I've looked at both your code and Michael's and I'm very impressed. You've gone much further than I have in the whole distribution side of things, and Michael's code for extracting and compressing the code is much cleaner than mine (I didn't know about the rpmlib functions).
There's really not much of anything I can add except the fact that I'm dealing with the RPMs on a file by file basis, which means you don't necessarily have to have the original RPM when applying the patch. You just have to have installed it on your system.
Anyhow, I don't know how likely that scenario is, but if you want to look at my code, it's at http://www.lesbg.com/jdieter/rpmpatch/files. I've included rpms, source rpms, and tar.gz's, so take what you need. cx_bsdiff is not my creation at all and is available from SourceForge. rpmpatch is the actual program that does the patching, but I realize that name is already taken by some other utility. I will switch names if anything comes of this.
If I was going to take this any further, I would switch to edelta (thanks Florian) as it seems to give equivalant compression to bsdiff at much less memory cost, and I would probably convert Michael's archive extraction code to Python and use it instead of my ugly rpmgzip module.
But, like I said, there's not much point in using my system if we figure most people keep their RPMs handy.
Jonathan