Well, methods are looked up in package tables, not in objects.

So you have basically three options:

1. create a new subclass per object into which the new methods go, and rebless the objects into their respective classes
2. Carry around a custom method table (for example a hash) in the instance data of an object, and define an AUTOLOAD sub that considers this custom method table as a fallback
3. Look what CPAN has to offer; somebody likely already implemented either approach.