^{Accepted status notwithstanding, I'm now convinced this answer is wrong. (I hope to improve it soon, after consulting with the OP about the accept.) I think I recall others saying this worked, but I believe their problems were at least slightly different. The method described herein remains valuable for some situations where chmod -R 777 /usr/bin is interrupted with Ctrl+C or otherwise does not complete. But once it does, pkexec is un-setuid'd too and it won't work any better than sudo, as Damien Roche and Oli have rightly commented.}

On an Ubuntu desktop system, PolicyKit is installed, so pkexec can be used to repair a broken sudo executable or sudoers file. You do not need to boot into recovery mode and you do not need to boot from a live CD. You don't even need to reboot.

In this case, run the following commands:

pkexec chown root:root /usr/bin/sudo

pkexec chmod 4755 /usr/bin/sudo

See this question for more information.