"handles" would not work too, because I know the eventual method names only at runtime and they may change.

Moose doesn't have anything to help you out with this, and honestly, changing method list at runtime is a serious design smell. You don't want the method list of RecordSet to be continually changing every time you make a new instance of a different table.

Also, why aren't you using one of the perfectly good ORMs out there? DBIx::Class? Fey::ORM? Rose::DB::Object?