The other option, if you can't conveniently get to environment variables (eg, under a web server) is to use the -I flag on the command line:
From the perlrun page:
<cite> -Idirectory
  Directories specified by -I are prepended to the search path for modules (@INC)</cite>...

Of course, then you've got to get the flag to the script, which means either typing it (in which case you can get to the environment), or putting on the end of the #! line which means altering the script, which you want to avoid. But at least it's the first line, so it's easy to mangle with some pre-processor code.