Nun, mein Server konnte nicht herausfinden, wie man ein Sudo-Paket findet, aber ich könnte es von der Ubuntu-Paket-Site :
wget http://security.ubuntu.com/ubuntu/pool/main/s/sudo/sudo_1.8.16-0ubuntu1.4_amd64.deb`
gefolgt von
dpkg -i sudo_1.8.16-0ubuntu1.4_amd64.deb
hat den Trick für mich gemacht. Ich konnte das Sudo-Paket ohne Sudo erneut installieren, indem ich mithilfe von SSH eine direkte Verbindung mit Root mit einem vorkonfigurierten SSH-Schlüssel herstellte.