|more useful options|
Apache's config lets you specify where a cgi can execute but since you're on shared hosting, you are not likely to be able to change use of a cgi-bin dir inside public_html.
You can, however, in most1 shared hosting setups using Linux and Apache, access the directory ABOVE public_html, via ftp or ssh, and put your /lib there. I suggest you do it that way, IF (and only "if") you really need to install (non-core) modules which the host has not already provided or which you've created yourself. Your answer, elsewhere, does not yet clarify whether you are talking about self-built, core, or other modules.
In any case, you really need to to keep executables
Re your comment that "I think this is a problem with FP, not Perl", I think I'd be more inclined to view this as a problem with some misconceptions or blindspots on your part about directory structures, server configuration, and perl.
Since, as you provide details you're getting more useful responses here, press on!
1 Qualify this and -- where unclear -- much of the rest of my remarks with the phrase "in my experience" or "to the best of my knowledge" unless a statement is accompanied by a cite of a standard reference.
In reply to Re^5: MS Frontpage, _vti_cnf directories and perllibs