Thanks a lot! The relocatable @INC was the key I was looking for.
Now I am using the PAR::Packer to build a PAR archive, then I decompress the PAR archive, add a relocatable perl executable (and the perl.dll on Windows) to the soup and I am done.
Vojtech