In theory, you could modify the binary loader to patch everything it loads by means of a database.
While this wouldn't catch anything loaded by other methods or self-modifying code it would probably work on 95% of the software. However, we'd have a very hard time building the patch database (which would require automated code search and visual inspection of candidates).
While I disagree with Piru that it wouldn't work entirely, he does have a point that compatibility is limited. Also, you've brought up something that always really bugged me. Self modifying code. Without a doubt one of the worst programming practices I've ever run into.
And impossible to patch for.
The first thing anyone following this idea of mine is going to have to accept is that OS' like MorphOS willl have BETTER compatibility with Amiga 68K code then a Coldfire based re-implementation.
The MorphOS JIT compiler can handle on the fly translation of 68K instructions.
The approaches needed for a slower processor like the Coldfire include the CF68KLib library to trap unsupported instructions, patching binaries before execution, possible 68K emulation software (much slower than a PPC), and recompilation.
It can be done, but some software simply isn't going tp run on a system like this.