Was the cgi-bin there when you took out the hosting plan, if so, then perl is installed on the server. the path is either
/usr/bin/perl or /usr/local/bin/perl your provider should give you this information. There are servers like the cobalt RaQ which allow you to run perl scripts from anywhere on your site.
Start off with this script http://www.scriptsolutions.com/programs/free/perldiver/
upload this script to your cgi-bin in ASCII format and set the permisions to 755.
When you run the script it will give you the perl version and modules installed.