"So you really need an automatic re-linker of some sort and probably a new binary format that can be re-linked, and some infrastructure to keep track of what binaries exist on the system and what they depend on. Plan 9 never had that."

Plan 9 has all of those things. Namely 7l† and mk††.

† http://plan9.bell-labs.com/magic/man2html/1/2l

†† http://plan9.bell-labs.com/magic/man2html/1/mk