Prelinking can change binaries as well. A combination of a Mandatory Access Control system (SELinux, AppArmour) and a Host Based Intrusion Detection system (like AIDE) could respectively help prevent and detect changes to binaries.

I'm not entirely sure if techniques such as ASLR are fool-proof enough to prevent changes to binaries in memory - I haven't studied enough about ASLR yet.