You can do pretty radical modifications of code too if you're willing to move it somewhere else to get the room to enlarge things. It turns out that almost all x86 instructions are position independent; there's only a few that are. Then you jump from the original location to the patch, run the patch, and jump back.

Gratuitous plug - that was my doctoral research (among other things, hot-patching in safety checks on a running Apache binary), and I wouldn't mind seeing it get used for a good purpose. The code's available at www.dyninst.org.