For UNIX you can use the following shebang (from perlintro), and it should work regardless of where the interpreter is, provided that it is in the path:
As far as I know env should be always in the same place.
I heard that it's not in the same place on all systems. It definitely does not exist there in Windows (which is the important part of the question, since perl is probably in /usr/bin on the unix box).