par can do what you want; just follow the documentation to get one big executable containing your script and all of the modules it uses. Keep in mind that if any of the modules aren't pure-perl, you'll have to build them on a platform identical to the one at your hosting environment.

I usually deal with modules in hosting environments by creating a ~/cgi-lib/perl5 directory to upload my modules into, then putting use lib '/path/to/home/cgi-lib/perl5' near the top of my script. I'm not sure what problems you keep running into with building them; see Re: Re: Alternatives to User::Agent? for a useful technique.