A rescue mode built around an initrd would be quite useful to deal with situations like this without resorting to a boot CD. Ubuntu had some fairly complex instructions on how to boot from the initrd and fix the problem from there, but these did not work on my system.
Probably something with busybox should do the trick. I guess there already are complete distributions built this way, but it would be nice to have e.g., Ubuntu install this as a boot menu option.
Something initramfs based, using a statically linked busybox, would probably be at least a good start. Hopefully it would not make the initramfs much bigger, but if it does, there are probably ways to get around it. I especially like the idea of not requiring a CD to boot from. --liw
What would be the harm in building a static linked dpkg? I suffered the bug, but I already keep a second, stable partition installed on the same drive. I also wish there was a smarter way to handle grub / MBR in this instance. --jldugger
Static linking has at least a security maintenance problem: a statically linked binary needs to be re-linked every time there's an update to any of the libraries it links to. Otherwise a security problem fixed in the libraries won't be fixed in the application itself. However, if static linking is otherwise the best solution, the re-linking issue can be solved, I'm sure. A simple way of doing that would be to ship the .o files for the application in the .deb, and then hook into dpkg in some way so that the application gets re-linked when necessary.
A separate partition in an interesting idea, which might warrant some pondering, if someone wants to start developing a rescue approach. I don't currently have time for that, alas. --liw