If you want to do modernish Perl web development in CGI space, then I'd go with CGI::Application. "Modern" frameworks typically require you to use some sort of proxying to a backend service/port.

Shared hosting plans will make it difficult for you to have the control of ports and proxying that you seek.

You can also look at maintaining your own server in the cloud, e.g., Linode.

Finally, if you want to take a look at hosts that will definitely have Perl on their system one way or another, you can look at https://partnernoc.cpanel.net/. Keep in mind the majority of these places provide shared hosting, but there shouldn't be too many restrictions in place to you setting up your own Perls using local::lib and perlbrew other than disk space restrictions in that environment.

(disclosure, I work for cPanel)

Update:

FWIW, in the spirit of dog food eating I have my own WHM server that I use for application development rather than for shared hosting. It's a pretty nice way to go if you tend to want to various personal projects going at the same time rather than use it strictly for providing shared hosting accounts. You can do that, too; but having full control over the server is nice. Some applications are CGI/CGI::Application, some are Dancer; some are UI, some are RESTful services. From someone else, what you get just depends on how much control you can wrestle from your shared hosting provider. If you are your own shared hosting provider, then the sky is the limit. WHM gives me about 99.9% of what I need for this purpose, including DB management.