If you are willing to ship binaries, the usual answer would be: use PAR;. You can also install .par files into the local system using PAR::Dist. To solve the bootstrapping problem (no PAR::Dist on the target system), you can just include that (pure-Perl) module into the installer script. Then it requires either Compress::Zlib and Archive::Zip to be present or an "unzip" tool. ActiveState's Win32 perl includes those modules. Unix usually has an unzip. Perl 5.10 will always include Compress::Zlib and Archive::Zip is pure-Perl and thus it's possible to inline it into the installer script. For an example, check out the local-path-installer script I hacked up for bugzilla .
As for the problem of the original poster: You could check out Adam Kennedy's "pip" tool.