Estou surpreso que você possa até mesmo inicializar. O Python é uma parte integral do sistema que mesmo ubuntu-minimal depende dele. A remoção através do gerenciador de pacotes não é possível. Eu não estou surpreso que você não possa fazer coisas.
Seu problema agora é que para reinstalar esses arquivos, você precisa de coisas como gerenciadores de pacotes para funcionar. Mas eles exigem que o Python esteja lá de alguma forma. Você provavelmente poderia tentar espelhar sua instalação e depois copiar todos os arquivos que você apagou ... Mas entre o tempo que levaria, e os outros problemas que você provavelmente iria encontrar ao longo do caminho, eu acho que é provavelmente uma perda de tempo. Certamente quando a outra opção é muito mais rápida.
É possível que você não tenha feito tanto dano quanto você afirma (é por isso que é importante seguir os comentários sob sua pergunta e nos fornecer o máximo de informações possíveis sobre o evento), mas se as coisas estiverem tão quebradas como eles parecem, você fez um ótimo trabalho - e minha resposta acima está.
A mensagem para viagem, aqui: Parabéns, você pode reinstalar.
Eu sou britânico, então isso pode parecer mal-humorado ou condescendente, mas honestamente não quero dizer isso dessa maneira. Eu quebrei dezenas de computadores ao longo dos anos fazendo coisas como esta. É assim que nós aprendemos. O que você fez é bastante terminal, mas não há vergonha aqui. Agora você sabe que não deve fazer isso novamente.