OP: Aparentemente deletar o python3 foi um dos erros mais burros que eu poderia ter cometido. Eu não pude reinstalá-lo porque parece que muitas funções básicas (incluindo a instalação de pacotes) dependem do python3. Ele até quebrou minha GUI quando reiniciei meu computador. Felizmente eu ainda era capaz de fazer backup de meus dados e fazer uma re-instalação quase indolor do Ubuntu 14.04 (sem bagunçar minhas outras partições). Eu acho que tive sorte.
Resposta curta para outros usuários Linux inexperientes como eu: NÃO desinstale o python3 ou qualquer outro programa pré-instalado, a menos que você saiba absolutamente o que está fazendo. Sempre. A menos que você esteja disposto a desperdiçar metade do seu dia fazendo backup de seus arquivos e reinstalando o seu Ubuntu.