In addition to AnomalousMonks advice of a test suite, I would suggest at the very least to invest the time up front to run automatic regression tests between whatever development version of the program you have and the current "good" (but ugly) version. That way you can easily verify whether your change affected the output and operation of the program. Ideally, the output of your new program and the old program should remain identical while you are cleaning things up.

Note that you can enable strict locally in blocks, so you don't need to make the main program compliant but can start out with subroutines or files and slowly convert them.

For your second question, have a look at Exporter. Basically it allows you to im/export subroutine names between packages:

package x;
use Exporter 'import';
our @EXPORT_OK = ('a', 'b', 'c');
[download]

#main_script
use x 'a', 'b'; # makes a() and b() available in the main namespace
[download]

To find and collect the global variables, maybe it helps you to dump the global namespace before and after your program has run. All these names are good candidates for being at least declared via our to make them visible, and then ideally removed to pass the parameters explicitly instead of implicitly:

#!perl -w
use strict;

our $already_fixed = 1; # this won't show up

# Put this right before the "uncleaned" part of the script starts
my %initial_variables;
BEGIN {
    %initial_variables = %main::; # make a copy at the start of the pr
+ogram
}
END {
#use Data::Dumper;
#warn Dumper \%initial_variables;
#warn Dumper \%main::;
    # At the end, look what names came newly into being, and tell us a
+bout them:
    for my $key (sort keys %main::) {
        if( ! exists $initial_variables{ $key } ) {
            print "Undeclared global variable '$key' found\n";
            
            my $glob = $main::{ $key };
            
            if( defined *{ $glob }{GLOB}) {
                print "used as filehandle *'$key', replace by a lexica
+l filehandle\n";
            };
            if( defined *{ $glob }{CODE}) {
                print "used as subroutine '$key'\n"; # so maybe a fals
+e alarm unless you dynamically load code?!
            };
            if( defined *{ $glob }{SCALAR}) {
                print "used as scalar \$'$key', declare as 'our'\n";
            };
            if( defined *{ $glob }{ARRAY}) {
                print "used as array \@'$key', declare as 'our'\n";
            };
            if( defined *{ $glob }{HASH}) {
                print "used as hash \%'$key', declare as 'our'\n";
            };
        };
    };
}
no strict;

$foo = 1;
@bar = (qw(baz bat man));
open LOG, '<', *STDIN;
sub foo_2 {}

use strict;
[download]

The above code is a rough cut and for some reason it claims all global names as scalars in addition to their real use, but it should give you a start at generating a list of undeclared names.

Also see Of Symbol Tables and Globs.