I host my things at Bluehost.com. They have very quick and helpful tech support. Through cPanel you can install Perl modules in your account, and you get SSH access also. They run Perl 5.8.8, I think.

They are, like grengeeks, on the inexpensive side of the spectrum. No mod_perl, though (that I know of).

I am a happy customer, as you can tell.