Virtual hosting and colocated hosting are so cheap now that shared-server web hosting services have to cut back on services.
So shared-server web hosts focus on the features that the cheapskates of the market prefer, and offer very little custom support. This means that they focus on PHP and MySQL—no Perl, especially no mod_perl, no Python, no Ruby.
Look for virtual server hosting – you can probably find something in the $30—$50 a month range, which is more than you’ll pay for cut-rate shared-server web hosts, but you’ll actually be able to install the software you need.