You might want to try prohosting.com. They allowed (the last time I used them, anyway) CGI scripting in Perl. In order to be safe, they lock down pretty tight, basically chroot()'ing you to your homedir and restricting what modules can be used, although you can install modules that don't need compiling ( i.e., all Perl, no XS) in your home directory.

--
IndyZ