Your hosting company sucks. CPAN installs all dependant packages automatically. Or, if they use a lame packaging system such as RPM, that can install the dependencies automatically too. A new hosting company is what you need, not new packages.