Contrary to the old saying, you can fit a square-peg into a round hole. There are a couple ways to do it but they involve cheating. You can glue a square-peg onto a round-peg and use the round-peg as an adapter, or you can cut a square into the hole. If you want to cheat incrementally you can treat these two strategies as steps -- do them one after the other.
Suppose that you have two unrelated classes: an older one which is used pervasively in your system and a clean new one with a different protocol. You'd like to replace the old one with the new one but you don't want to break the system at any time during the transition.
Here is a way to do it:
This refactoring seems to work well when your old class is a leaf near the top of a hierarchy. If your old class depends upon a superclass for various features, you will have to verify that you can graft your new class between them without breaking anything. If this looks too hazardous, consider whether replacing the old class is really a good idea; it is probably better to clean it up in place.
An alternative would be to introduce the new class as a delegate of the old class, testing as each method is delegated, and then ReplaceDelegationWithInheritance and CollapseHierarchy. I like the superclass trick because it forces some issues to the foreground.