perlbin is simple and easy to use. You don't have to pay for perlapp or perl2exe anymore. Unlike App::Packer and PAR, perlbin ought to work on *any* version of perl (in theory, but Module::ScanDeps might not).

The idea behind perlbin comes from Ultimate binary wrapper.
The magic paragraph which somehow escaped me before is:

(Here we use the fact that
ZIP files remain ZIP files even if you prepend anything to them, and on
most systems executables stay executables even if you append anything
to them)
And that's all perlbin is. A small stub executable (about 20k) requireing a perl dynamic link library (about 700kb) and whatever else you use and BAM, you can package it (rpm, tarball, zip file, or whatever) and distribute it without any worries.