Can just use the fully qualified name to overwrite the sub.

Unfortunately not - the change is visible within your script, but not within the module.

Foo.pm

package Foo;
use warnings;
use strict;

sub ONE () { 111 }
sub TWO { 222 }
my $three = 333;
sub THREE () { $three }

sub go {
    print "One=", ONE, ", Two=", TWO, ", Three=", THREE, "\n";
}

1;
[download]

test.pl

use warnings;
use strict;
use lib '.';
use Foo;

#BEGIN {
    #*Foo::ONE = sub () { 444 };
    #*Foo::TWO = sub { 555 };
    #*Foo::THREE = sub () { 666 };
    sub Foo::ONE () { 444 }
    sub Foo::TWO { 555 }
    sub Foo::THREE () { 666 }
#}

Foo::go;
print "One=", Foo::ONE, ", Two=", Foo::TWO, ", Three=", Foo::THREE, "\
+n";
[download]

See also perl -MO=Deparse Foo.pm.

Update: sorry, this is rubbish - see Re^5: How to redefine a modules private function?

Can't get AnyEvent installed ATM, but your little demo does work, if you don't "re"define it, but define it before you load the module:

Foo.pm as in your example

test2.pl

use warnings;
use strict;
use lib '.';

BEGIN {
    sub Foo::ONE () { 444 }
    sub Foo::TWO { 555 }
    sub Foo::THREE () { 666 }
}

use Foo; # _after_ your "re"definitions

Foo::go;
print "One=", Foo::ONE, ", Two=", Foo::TWO, ", Three=", Foo::THREE, "\
+n";
[download]

What output do you get? Because I get

Constant subroutine ONE redefined at Foo.pm line 5.
Subroutine TWO redefined at Foo.pm line 6.
Constant subroutine THREE redefined at Foo.pm line 8.
One=111, Two=222, Three=333
One=111, Two=222, Three=333
[download]

which is what I would expect, since loading Foo.pm redefines the subs to the values that it has (111, 222, 333), not the values that we want (444, 555, 666).

Nice. And other post with more about it.