Some places run anything with a .cgi extension according to its shebang line. Others allow files with the executable bit set to run as CGI, or in any case files with certain extensions like .pl with executable bits set to do so. You're not likely to find mod_perl on shared hosting, though. You're also about as likely, if not more likely, to find Apache 1.3.3x as 2.x.x for that matter.

A small-to-medium local ISP is usually the easiest place to find shared hosting of a thoroughly modern bent. This is because they typically care enough about existing customers that they don't force incompatible upgrades across all their boxes. Then, when they build new servers, they try to get all the releases as recent as they trust to be stable so those new servers will be as close to current for as long as possible. Unfortunately, local ISPs are getting hard to find and you'll often be hosted on a single box with a single hard drive with some teenager at the helm. Keeping local backups is a good idea anyway, though. You also often have to wait until their old servers reach capacity and they're racking up more servers, as they won't put a new server up just randomly.

A VPS is definitely an option. Many of those by default still use Apache 1.3 as well, but you can find ones that use 2.x or you can upgrade it yourself (after all, it's your VPS). It's cheaper than any dedicated hardware server.

One thing people aren't entirely honest about with PHP is the idea that it's always mod_php. Often, especially on certain well-known bulk shared hosters, the PHP stuff is run as CGI scripts running as the owner of the content. That means that if you need a page's script to save data to your web space that you can do it with secure permissions, so that's a plus. It's not running within the Apache process, though, so you're not looking at the performance gain of doing that. Some hosting providers can give you choices in this regard, but some will just set you up the way everyone else is set up.

Not to pimp myself, but my partner and I sell hosting so I can give you some details and pricing for comparison if you like.