Zaxo's answer is probably the best for just using a pre-call hook. But if you need a little more control over calling the old sub, you may need to do it yourself.

I don't see the problem with strict. Just turn off strict refs locally and use symbolic references, it's a lot easier than messing with eval. Part of strict is knowing when you should turn it off. Messing with the symbol table is one of those times. Just make sure you don't turn off strict refs inside that closure that becomes the new sub, though.

package Foo;
sub bar { print "Original Foo::bar\n"; }

package main;

sub switcheroo {
    my ($pkg, $func) = @_;

    my $old_ref = do {
        no strict 'refs';
        \&{"$pkg\::$func"};
    };

    my $new_ref = sub {
        print "New $func\n";
        $old_ref->();
    };

    {
        no strict 'refs';
        *{"$pkg\::$func"} = $new_ref;
    }
}

Foo::bar();
switcheroo("Foo", "bar");
Foo::bar();
[download]

You may also want to use goto &$old_ref in case the original sub wanted to look at caller.