Would it be possible to do the actual re-defining at a later stage (say, CHECK or INIT)?

Something like this:

package ImportLater;

use strict;
use warnings;

our %overrides;

sub import {
    my $class = shift;
    my @functions = @_;
    my $cpkg  = caller;

    $overrides{$cpkg} = \@functions;
    return;
}

# For demonstration purposes only. This is where you'd do your stuff
sub override_functions {
    for my $pkg( keys %overrides ) {
        print "$pkg: @{$overrides{$pkg}}\n";

        foreach my $func ( @{$overrides{$pkg}} ) {
            no warnings 'redefine';
            no strict 'refs';
            my $orig = \&{"$pkg\::$func"};
            *{"$pkg\::$func"} = sub { 
                print "before $func\n";
                return $orig->(@_);
            };
        }
    }
}

INIT {
    override_functions();
}

1;
[download]

Use it like this:

#!/usr/bin/perl

use strict;
use warnings;

use ImportLater qw/ foo bar /;

sub foo {
    print "I'm foo";
}

foo();
[download]

Running that outputs:

main: foo bar
before foo
I'm foo
[download]