As Roger said, I still can't say I understand the problem. If you are compiling with something like PAR to generate a stand alone executable, then you won't need Perl at all. Perhaps your perl script is doing something like exec'ing Perl within itself? Perhaps that could be removed?

This may not be related to your question, but in systems where you don't know where perl is installed, you can usually get away with using the following as the shebang:

#!perl
[download]

This will execute whatever perl is in your path. If you need to see if Perl exists or not, Roger made a good point...write a shell script to do it. /bin/sh is always going to be there on Unix-ish platforms.