I went out and saw a really stupid cheesy movie with someone, and it got my mind off of this project (for the first time in a few weeks I think) long enough for some subconscious something to kick in. After getting home I was immediately aware that avoiding the make process was the mistake that led to this mess. It just took some time away from it for it to sink in after you mentioned it. My path is clear now, I need to:

1. Make a simple /bin/sh script (lets call it Installer.sh) that will run on any remotely reasonable *nix system and detect the latest available perl from the finite list of possibly directory paths. Then it executes something akin to "/some/where/perl Makefile.PL && make && make test && make INSTALLDIR=$1 install" with the appropriate perl. This isn't hard to do by sticking to pure bourne shell constructs and simple tools like basic grep.
2. Get a perl-style Makefile.PL built up for this project, and customize it so that it transforms #!/usr/bin/perl on the scripts to the perl that was used during the make, and so that it can be told what directory to install the software to, and transform some push(@INC,'...') line in all the scripts to point at a library directory located there, like what you described
3. Profit! (or at least, keep my job :) )

Anyways, thanks, your mentioning of using the standard perl Makefile.PL stuff and those variables got me thinking straight(er).