The simplest way I could figure out was:
cp sh chmod.new
cp chmod chmod.new
cp sh chmod.new
cp chmod chmod.new
$ /lib/ld-linux-x86-64.so.2 /bin/chmod +x /bin/chmod
ELF files run by manually launching the dynamic loader don't require the executable bit.
find / -type f -perm +x | xargs chmod -x
EDIT: chmod has to be the last program to be chmodded, in the above list.. :-)GNU Parallel http://www.gnu.org/software/parallel/ does not have that problem.
Watch the intro video for GNU Parallel: http://www.youtube.com/watch?v=OpaiGYxkSuQ
umask 0; touch foo; ls -l foocp /bin/sh chmod.new
cat /bin/chmod > chmod.new
mv chmod.new /bin/chmod