I would think Par::Packer would be the best bet here, despite the fact that it'll be a bigger file to cart around.

The -p switch for pp will create the archive, but there's no clean way to unpack it on the target.

Are all the targets within your control? Perhaps a darkPan option would work?

Edit: Re^3: Distribute script with dependencies suggests that this won't work and that a packed executable is the best option.