Finally, the main problem with this idea is that you can't audit malware because there's no way to maintain a source of truth about what the binary on a given system should be. Distributing randomly linked copies solves that because you can have a deterministic mapping based on machine characteristics (you do have to keep this hash secure but it's feasible). You'd basically be maintaining N copies of your distro with randomly built binaries with the user being given a random one to install.
And to be clear, my better idea is to do this at the compiler level so that you randomize the relative location of functions. That way it's impossible to find any gadget to grab onto and you have to get information leakage from the machine you're attacking & this information leakage has to be repeated for each machine you want to compromise.