It's not that they disallow Perl, just server modules like mod_perl. Setting up mod_perl to run with the permissions of each individual user is non-trivial most shared-hosting ISPs are not willing to tackle it.
I was actually under the impression that mod_perl wouldn't ever be safe for shared hosting until something like the perchild MPM was finished. Did this change recently?
If you run a mod_perl server for each user and proxy requests to it, you can give everyone their own mod_perl which they can restart and have a very similar model to FastCGI. I don't think ISPs will ever bother to do this though, and I know I don't have any interest in using a shared host.