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.