You can send back an object and store it in a lexical. Then when it goes out of scope, the object gets DESTROYed, you can restore the old value:

package Localize;

sub new {
    my ($self, $sub, $coderef) = @_;
    no strict 'refs';
    local $^W;

    my $oldval = \&$sub;
    *$sub = $coderef;
   
    bless [ $sub, $oldval ], $self;
}

sub DESTROY {
    my $self = shift;
    no strict 'refs';
    local $^W;

    my ($sub, $coderef) = @$self;
    *$sub = $coderef;
}

#############
package main;

sub foo {
    print "Real foo!\n";
}

foo();
{
    my $l = new Localize "main::foo", sub { print "Fake foo!\n" };
    foo();
}
foo();

__END__
Real foo!
Fake foo
Real foo!
[download]

This is similar to what Hook::LexWrap does, but it replaces the entire sub instead of adding pre/post wrappers.

Update: Speaking of this problem, I was wondering if anyone savvy with the internals can say whether or not it's possible for a sub to place a (anonymous) lexical onto the caller's pad, so that you can set up a callback via DESTROY for when the calling scope ends? I think this would be (insane but) cute -- you could even make a version of local for lexicals.