Has probado con:
apt-get install wicd-gtk
Si ha eliminado networkmanager directamente no tiene conexión a internet y por lo tanto no puede utilizar
apt-get para instalar nada que no tuviese instalado anteriormente y cuyo .deb siga en el sistema. La otra alternativa es que, si tiene la iso que utilizó en la instalación o puede conseguirla de alguna manera, utilice
apt-cdrom. Así que lo primero que tiene que hacer es recuperar la conexión, y si ya tenía instalado
networkmanager es posible que por algún lado del sistema esté el .deb correspondiente y que pueda reinstalarlo utilizando el comando que le he dejado en la primera respuesta que he dado. Si esto falla puede utilizar, como ya he dicho, alguna iso que pueda conseguir de alguna manera instalar bien
wicd bien
networkmanager para poder recuperar la conexión. Para más información
man apt-cdrom.