I think #!/usr/bin/perl /usr/bin/perl/myscript.pl is not ugly.

The other way is to create a small C program that does nothing but execs perl to run that script. Than you can put the name of that binary in the shebang line.

Yet another way is to use a bash or perl script like

#!/usr/bin/perl -w
*ARGV = *DATA{IO};
do "/usr/bin/perl/myscript.pl";
__DATA__
[download]

or a shell script like this:

#!/bin/sh
perl /usr/bin/perl/myscript.pl "$0"; exit 0
[download]

and make perl script the first lines, or just

#!/bin/sh
perl /usr/bin/perl/myscript <<ENDDATA; exit 0
[download]

if you don't need to seek in the file.