Have you searched CPAN for modules that walk the symbol table? The following will find all subs currently existing in a package. It can be expanded to walk the entire symbol table. It can be expanded to look at @ISA. There's no way to know whether the subs it finds are methods or not.

use strict;
use warnings;

use Scalar::Util qw( reftype );

sub is_glob {
   for (@_ ? $_[0] : $_) {
      return reftype(\$_) eq 'GLOB';
   }
}

sub get_subs {
   my ($pkg) = @_;
   my $symtab = \%::;
   for (split /::/, $pkg) {
      $symtab = $symtab->{"${_}::"}
         or return;
   }
   return grep is_glob($symtab->{$_})
            && *{$symtab->{$_}}{CODE},
          keys %$symtab;
}

print "$_\n" for sort +get_subs('Foo::Bar');
[download]

Interesting tidbit: 'Foo::Bar' can be written as Foo::Bar::.

What other kind of code (besides string eval) can generate methods on the fly? Can we recognize them in a reasonable way?

Assignment of a sub ref to a glob.