For the redistributable part, you can also consider to use strawberry perl notably the portable editions: you can modify a portable edition adding what you need via cpan or adding separate executables in, let's say, the /strawberry/perl/bin folder. You can play with the portableshell.bat file that come with the distribution and after that repack in a compressed file.

citrusperl is a tool that is very near to your needs: but I have just tried it in the past and it is focused in Wx GUI applications, but can create a customized Perl distribution usable on windows machines.

For stand alone executable PAR is the base choice and cavapackager can be an alternative.

Let us know your achievements!

L*