Here's what I'm doing in (hopefully soon-to-be-CPAN'd) Thread::Apartment, using Class::ISA and Class::Inspector:

use Class::ISA;
use Class::Inspector;

sub introspect {
    my $obj = shift;
    
    my $base = ref $obj;
    my @isa = Class::ISA::self_and_super_path($base);
    my %method_hash = ();
#
#    get simple methods names first
#
    my $methods = Class::Inspector->methods($base, 'public');
#
#    then get fully qualified ones (ignoring our local methods)
#
    foreach my $class (@isa) {
        next if ($class eq $base);
        $methods = Class::Inspector->methods($class, 'public');
        $method_hash{$class . '::' . $_} = 0
            foreach (@$methods);
    }

    return (\@isa, \%method_hash);
}
[download]

(That's actually a pared down version, but has the relevant bits for your question)