Did you read any of the links that the Anonymous Monk gave you? They show plenty of ways to include CPAN modules, even when you think you cannot.

I use shared hosting, but my ISP provides a CPanel interface to install modules from CPAN, so "shared hosting" is not a barrier -- even cheap shared hosting (mine's on the order of $5/month).

Further, as those links would explain in better detail and with more alternatives, if you have the capability to write your cgi script onto your host, you have every privilege required to include a pure-perl CPAN module: if you upload script to /home/username/www/cgi-bin/myscript.cgi, then you could create the directory /home/username/www/cgi-bin/lib/, and place the .pm files appropriately in that directory, and just make sure that myscript.cgi includes use lib './lib/';. If you also have SSH or other shell access, you most likely also have access to a compiler, and can probably install even non-pure-perl modules in that subdirectory.