Parece que você não desinstalou o pacote que fornece o executável gem , portanto ele ainda está em /usr/local/bin/ e aponta para o interpretador /usr/local/bin/ruby que não está mais presente.
Você pode desinstalar esse pacote (recomendado, já que também removeu o pacote do ruby do qual ele depende) ou apenas certificar-se de que ~/bin esteja antes de /usr/local/bin no seu PATH . (Como alternativa, se você tiver acesso root, poderá executar novamente o script ./configure sem especificar --prefix=${HOME} e permitir a instalação em /usr/local/bin , que é o padrão do Ruby.)
Depois de organizar as coisas para que seu shell encontre o executável gem instalado em ~/bin , você deve ser capaz de simplesmente gem install rails sem precisar de sudo . (Ou, se você optar pela instalação raiz em /usr/local/bin , certifique-se de que gem esteja em /usr/local/bin/gem e, em seguida, execute sudo gem install rails , como você tentou antes).
Possivelmente, uma abordagem melhor seria ver rvm ou rbenv , que tornam o gerenciamento de vários rubis uma tarefa bastante indolor. Usando qualquer uma dessas ferramentas, você pode ter várias versões do Ruby instaladas sem a necessidade de remover o sistema, o que pode ser necessário por outros pacotes no sistema.