I think you'll have more luck with approaches more like FastCGI/mod_perl. There are things like PPerl which should be adaptable to installation on ISPs. The large CGI system MiniVend used an approach with a Perl daemon and a tiny stub CGI that calls it to avoid the overhead of compiling.