Wow! You hit the nail on the head there (and apparently opened a can of worms too! Better you than me).

That's pretty much where I'm heading. Self install Perl web apps that you simply place in your CGI directory, click and go. PHP'rs do it all the time. The code is bundled up with the CGI install script, which gets neatly extracted into the correct directories based on the running CGI env and help from the user. I see no reason why Perl can't do the same, provided you're not tied down to installing 3rd party modules in places the user doesn't have access to (or at the very least the self install could check for required modules and inform the user of what's missing).

BikeNomad had the right idea with the Self-extracting Perl archives code he posted (although I'm not sure why he felt the need to encode it).