Consider using PAR for your application. Either upload a .par file containing the required collection of modules, or go the whole hog and build an executable for your CGI. In either case, you should be able to verify that your app works before you upload it.

An alternative is to make install to a private directory tree of your own (perl Makefile.PL PREFIX=/my/dir LIB=/my/dir/lib), and put this directory tree into your webspace, adding its lib directory to @INC with use lib. This will ensure that the binaries are in the right architecture specific directories.