The authors of Perl recognize that there is a problem with relying on #! magic (though for different reasons than discussed before). This is conveniently documented in the perlrun document. For reference, the way to do it is:
#!/bin/sh
#! -*-perl-*-
eval 'exec perl -x -wS $0 ${1+"$@"}'
if 0;
In this case, Perl itself looks for the first line that starts with #! and also contains the string perl, so the first line allows execution on systems that do interpret #! specially, and the second is what Perl is looking for to verify that this is actually a Perl script and not a POSIX sh script.
The third line is simultaneously a complete shell command and an incomplete Perl statement. The shell command starts Perl with all the specific command line parameters and some options to force this special parsing. The interesting thing is that the Perl statement concludes with if 0 on the fourth line, causing the entire statement to be skipped when interpreted. Pretty clever, really.
However, we can do one better than this. Since #!/bin/sh isn't guaranteed to work, we'll tweak it a bit:
$ cat hello.pl
# this is a perl script
#! -*-perl-*-
eval 'exec perl -x -wS $0 ${1+"$@"}'
if 0;
print "hello, perl\n";
$ sh ./hello.pl
hello, perl
$ perl ./hello.pl
hello, perl
$ chmod +x hello.pl
$ ./hello.pl
hello, perl