IMO the simplest way is:

$ /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.

I agree that this is easiest, and I'm surprised that the article calls it "hardcore" (slides 38-39). But it does bring to mind a more devious challenge: Someone ran "chmod -x ld.so"...

What about:

  find / -type f -perm +x | xargs chmod -x

EDIT: chmod has to be the last program to be chmodded, in the above list.. :-)

Your use of xargs can lead to nasty surprises because of the separator problem http://en.wikipedia.org/wiki/Xargs#The_separator_problem

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

GNU Parallel isn't needed to avoid this, using find's -print0 and xargs's -0 would suffice. The advert is unwarranted.

The parent seems simpler. More importantly, it works on just about any Unix.

Couldn't you just set an appropriate umask and then make a copy of chmod?

I don't think umask setting affects the executable bits of files, just directories. You can try by entering something like

  umask 0; touch foo; ls -l foo

It does affect files, but umask only subtracts permission bits. So if the program creating the file doesn't try to set it executable, then umask will never change that.

My first thought was pretty similar:

cp /bin/sh chmod.new

cat /bin/chmod > chmod.new

mv chmod.new /bin/chmod

My first thought was, just re-implement it in C, then I remembered than we do have a bunch of boxes without a compiler on.