It's very hard to find web hosts that offer full CGI scripting support.

It's not if you actually look for them. It will usually cost a bit more than a package without CGI or PHP support, though.

My current package allows for 5 sites at about 200 euros a year, and that includes mysql, php, perl/CGI and mod_perl. I'm sure you can find cheaper packages for single sites (which may not include mod_perl).