Talvez uma maneira melhor de reinstalar o sistema operacional seja baixar o pacote python (e possivelmente qualquer pacote de módulos python) e usar rpm para instalá-los em seu Python atualizado.
O pacote python para o RHEL 6 deve ser python-2.6.6-64.el6.x86_64 , que deve estar disponível na Red Hat, ou você pode retirá-lo de um arquivo .iso do RHEL6. Provavelmente você terá que usar a opção --force no RPM, pois ela precisa substituir o pacote e todos os arquivos.
Depois disso, yum deve funcionar, embora alguns arquivos ainda existam da atualização do Python. Ao atualizar o Python, certifique-se de usar --prefix para instalá-lo em algum lugar como: /usr/local/python2.7.12 ou qualquer outro local longe dos arquivos Python do sistema.