I use Catalyst on DreamHost under fastcgi. It's $8/month if you pay up in advance. I've been there 6 years and run something like 40 websites (mostly static or script built, some CGIs, a handful of Catalyst apps). The service is fair, the control panel is good, the uptime is pretty good (but not business class), and the resources and such for the price are really good. Many hosts are supporting fastcgi now because Rails (and Catalyst at this point) is too slow to use without it. If they advertise that they support Rails, they almost certainly support Catalyst (if you admin your own modules with local::lib or similar techniques).

Seconded lukewarm recommendation for DreamHost. Been there almost as long and while I'm not 100% satisfied (shared server hosting FTL) I've been a bit happier after ponying up the slightly more per-month for a VPS. For personal stuff and/or just goofing around they're a pretty good value for the price; if I were to do something more "commercial" I'd go with someone like Linode (but then I'd have to do more sysadmin'ing myself).

The cake is a lie.
The cake is a lie.
The cake is a lie.

$lukewarm_recommendation++. That's a perfect description of how I feel about them. I really like DreamHost but it's a low expectations, feature list, ease of management kind of like. I also have a Linode account and it's wonderful, it's just a bit taxing for a systard like me.