You can't replace methods per-object, only per class or package. So instead, how about replacing the object's class! Let's assume that you want to replace the foo method in $object ...

    use Scalar::Util qw(refaddr);
    my $newclass = q[
        package $CLASS::FakeClass$OBJID;
        use base qw($CLASS);
        sub foo {
            my $self = shift;
            ... blah blah blah ...
        }
    ];
    $newclass =~ s/\$CLASS/ref($object)/eg;
    $newclass =~ s/\$OBJID/refaddr($object}/eg;
    eval $newclass;
    bless $object, ref($object)."::FakeClass".refaddr($object);
[download]

That creates a new class just for that object (the one-to-one class-to-object correspondence is guaranteed by using the object's address in memory as part of the class name), which inherits from the class that the object is already an instance of, then reblesses it. Any methods defined in the new class will override those in the original class, and any others will just be passed through to the original class in the usual way.

The one problem with this is that you'll need to be really careful if you serialise and later unserialise objects. In particular, objects are extremely unlikely to be unserialised at the same address in memory, which may lead to later namespace clashes.

Code is untested, but I do something similar quite often, so the principle is correct even if I typed it wrong :-)