Bottom line, you're paying for it, so ask.

I've been with Superb.net for over 2 years, and they have been very responsive to installing perl modules. pair Networks is also a perl friendly web host. merlyn suggested Sprocket Data in this node.

Update: Go to this node for a discussion of mod_perl and shared hosting; it also has some useful links for finding and evaluating Perl friendly web hosts.

HTH.

--
hiseldl
What time is it? It's Camel Time!