Another interesting strategy, particularly in the age of widespread use of VMs and containers, might be to extend the basic idea of ASLR beyond address space. Randomize paths and filenames and system call numbers, for example. You'd need to build all your binaries yourself, of course, and run scripts through some sort of mangler (for maximum effectiveness, do this per-VM/container). You'd want to encrypt non-user-visible strings, too.
There'd be a lot of tooling work necessary to make this practical in the real world, of course.
(Edit: Just found this, which looks relevant: http://research.microsoft.com/en-us/um/people/helenw/papers/... )
I've never heard of anyone actually using it. It would be a huge pain and wreak havoc on sysadmins. Also, really nasty attacks are capable of bringing exploit code with them.