Seu segundo problema mencionado (não é possível digitar no prompt raiz no modo de recuperação) sugere que há muito mais errado com sua instalação do que ser incapaz de usar o sudo. Eu sugiro que é provavelmente a maneira mais simples de fazer backup de seus dados pessoais (você deve ser capaz de fazer isso de um Live CD ou USB) e reinstalar o Ubuntu para obter um sistema limpo e funcional.
Desinstalar o sudo é quase certamente uma má ideia; Eu não tentei, mas é fundamental para o modo como o Ubuntu é projetado para funcionar (você não pode fazer qualquer coisa no modo privilegiado sem ele, em uma instalação padrão). Certamente não irá corrigir o problema com o modo de recuperação, e é provável que você desinstale tantos pacotes dependentes que você será forçado a reinstalar de qualquer maneira.