HardHat is another Perl friendly ISP - you get your own instance of Perl so you can install whatever modules you need via ssh. You also get your own instance of Apache(1.3.26) + mod_perl(1.26). Their cheapest plan is $10.63 per month.
(cron and Postgresql also included)