You've got quite a task on your hands. I've done this very task. I started by doing the obvious: use strict in the main routines. That, of course, boned the code. So i tried the opposite approach: starting from the libraries. I added use strict to library routines. It was slightly easier to have the code continue to work when coming from that direction. Also, it let me understand data flow in the code.
Then I did some more ambitious things: I found common subs and put them into a proper Library_name.pm file, and started to

use Library_Name qw(/subroutine_i_needed/);
[download]

This then took me the next couple steps. I started with use strict in the library.pm file, and I could start making the interfaces more like a properly built system. I didn't go all the way to object perl, the system did not really lend itself to that, but it did let me go to use strict fairly quickly.
Worst part was the templating code. it relied on eval's and globals. Very ugly. I ended up replacing the whole template stuff with some generic code that (later) I found was similar to the CPAN Templating stuff.
--
Jay "Yohimbe" Thorne, alpha geek for UserFriendly