Permission denied for all sudo comands

You should boot from a LiveCD then do the following:

Mount your Ubuntu installation by clicking on the device's icon in the file manager.
Open a terminal and cd into the /usr/bin folder of that installation you mounted from above.
Run this command to give all users execute permissions
```
sudo chmod -R a+x .
```
Run this command to give all users read permissions
```
sudo chmod -R a+r .
```
Run this command to remove all users (except root's) write permissions
```
sudo chmod -R o-w .
```
Reboot and see if it works.

Related