/bin
contém alguns dos arquivos mais básicos do seu sistema, e não poderá fazer muito sem ele (a inicialização não funcionará, o mesmo para instalar pacotes). Sua melhor aposta é inicializar um live cd da mesma versão do Ubuntu que você está usando, montar sua partição root exisitng e rsync seu /bin
over para essa partição.
Para uma limpeza completa, reinstale os pacotes afetados. Para descobrir quais pacotes reinstalar, use este comando:
find /bin -type f | xargs dpkg -S | sed -e 's/:.*//' | sort -u
E para reinstalá-los:
sudo apt-get install --reinstall $(find /bin -type f | xargs dpkg -S | sed -e 's/:.*//' | sort -u)