Tente fazer o download do pacote sudo
e instalá-lo manualmente:
# for 64bit system
wget http://security.ubuntu.com/ubuntu/pool/main/s/sudo/sudo_1.8.5p2-1ubuntu1.1_amd64.deb
# for 32bit system
wget http://security.ubuntu.com/ubuntu/pool/main/s/sudo/sudo_1.8.5p2-1ubuntu1.1_i386.deb
sudo dpkg -i sudo_*.deb
Se você não puder usar sudo
para executar o último comando, tente reiniciar no modo de recuperação e executá-lo como usuário root.