A good compromise would be if you could specify an object as being "replacable" and then it would have the extra layer of indirection (the table) to make it fast. That way you don't pay a penalty when you're not using that feature and/or don't have to walk the heap. It would also be better for security in that you'd have to explicitly state which objects were allowed to be replaced. You have to think about needing that feature in advance though.
I believe Squeak just adds the extra indirection when #become: is used, by turning the old objects into "forwarders". On the next full GC, the forwarders get cleaned up and the extra indirection removed.