I stopped being able to do a perlbrew install ...on my hosting service because of execution runtime limits...

perlbrew install -n Perl-5.20.0 will skip testing. Your application probably has its own test suite that is much shorter running than Perl's. If that suite passes, it may not be necessary to run the Perl install through its tests. ...maybe not an optimal solution, but it might be good enough until the host sees the light.

On one of my systems the install of Perl 5.16.3 takes about five minutes by skipping tests. Lowly Perl 5.8.9 takes about 2 minutes. Both fall within the 15 minute limit set by your host.