Install your scripts with the normal CPAN tools. During the build, they take the perl that you used to run the build script and inserts it into the shebang line. Also, you'll ensure that the perl you are using has the dependencies installed.
For instance, you have at the top of your script:
#!perl
Using the normal module distribution process (see my App::PPI::Dumper as an example),
$ perl5.10.0 Makefile.PL
Installing it, ExtUtils::Makemaker or Module::Build rewrites the shebang with the path of the perl you used with the build script:
#!/usr/local/perls/perl-5.10.0-rc2/bin/perl
eval 'exec /usr/local/perls/perl-5.10.0-rc2/bin/perl -S $0 ${1+"$@"}'
if 0; # not running under some shell
When you distribute your script as a complete distribution, you get all of the toolchain features for free, like automatic installation of dependencies. It makes life much easier.