We need to know what you can and can't do on the shared host. Errto
has assumed that you yourself can install modules on this server. Others may assume you can get the sysadmin of the server to install a module or two. swares
assumes you have a home directory and he points to some good documentation on how to use it.
From what you said, there is some directory that you can upload files to. If you don't have a home directory, but can create sub-directories, then you can create a directory "yourlib" to use in an analagous way to the '/usr/home/your_home_dir/lib/' directory in the guide that swares refered you to.
If you can't create directories, and you can't get the sysadmin to install modules, or create the directories you need, then you may be stuck. I don't know if Template::Toolkit can run with just Toolkit.pm in the local directory, using "use lib './';", but that's easy enough for you to try on the server.