For the second idea, updating references when the code moves is more directly used in a newer Chrome patch format: Zucchini [1]. Courgette does a complex process of disassembling, aligning labels, and sending a patch of the disassembly, so the patcher has to do disassembly, patching, and reassembly. Zucchini does a more straightforward disassembly pass to note where the references are, and then pre-patches them based on how it knows the code moved. Compared with Courgette, this involves less intermediate state so it's faster [2], the code is simpler, and because much more is implicit in the code motion the patches tend to be smaller.
That basic technique goes back at least to the TranslateAddress method in Exediff (1999) [3].
I've been meaning to write up an article on this stuff [4], Google doesn't seem interested in publicizing Zucchini themselves, maybe due to the patent kerfuffle around Courgette. Microsoft's document on delta compression [5] covers a lot of this ground.
[1] https://chromium.googlesource.com/chromium/src/+/HEAD/compon...
[2] Some of this can be avoided, I made some changes to Courgette for a significant speed increase here: https://bugzilla.mozilla.org/show_bug.cgi?id=504624#c39
[3] http://robert.muth.org/Papers/1999-exediff.pdf
[4] I did write up a bug to consider Zucchini in Firefox, with patch size comparisons, but ultimately we didn't switch from the simple power of bsdiff: https://bugzilla.mozilla.org/show_bug.cgi?id=1632374
[5] Their system can use info from the pre-linked objects and PDB symbol files for better alignment, I'd played around with seeding alignments like this in bsdiff and Zucchini but I don't recall it giving significant improvement. https://docs.microsoft.com/en-us/previous-versions/bb417345(...