Maybe what the OP is looking for is Par::Packer?
Or perhaps if he is using Active State Perl, he could try out the Perl Dev Kit (perlapp).

Hope this helps :)

EDIT: Nevermind, I have GOT to start reading all the way to the end of the question LOL!
You should check out the perl dev kit anyways :p It is easy to work with and will do /most/ of the work for you.