How to fix sudo after "chmod -R 777 /usr/bin"?

^{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.

Even when running from the live CD / Pendrive, you must prefix your chmod command with sudo. So your steps will be like the following:

1. boot from a live CD / Pendrive
2. check whether your disk was already automounted (and where to). If not, mount it (see below)
3. use sudo chmod 0755 <path> to adjust the permissions

How to figure out where your disk is mounted: from a terminal window, run mount (without arguments). This will list up all mounted devices. Check for the type listed -- you can skip everything not using a "real file system" (your disk probably uses either ext3 or ext4 -- you can for sure skip things like proc, sysfs and the like). If something sounds promising (looking like /dev/sda1 on /media/sda1 type ext3), check its contents using ls /media/sda1 to see if it's that.

If it is not mounted, you can check with the /dev entries where the disk could be (using ls /dev/ |grep '/dev/sd to check for available devices; your disk should look like /dev/sdaX, /dev/sdbX or the like -- with X being a number). Compare this with the list of mounted devices. If it's not there, try to mount it and check its contents (as shown above). To mount it, first create a mountpoint, e.g. sudo mkdir /mnt/mydisk, then try to mount the device using mount /dev/sda1 /mnt/mydisk and check its contents using ls /mnt/mydisk.

Once you get the right disk there, you can go to change the permissions back on your usr dir: sudo chmod 0755 /mnt/mydisk/usr.

Now you still might be in trouble if you originally ran the chmod command recursively, using the -R parameter. In that case you can either try to fix each entry manually -- or you can go straight for a fresh install...