Arreglando un paquete de dpkg y apt roto

Estoy trabajando en un VM que no he administrado en el pasado y está en mal estado (pero necesito rescatarlo). No soy un experto en linux, pero en los últimos 5 años he podido solucionar problemas utilizando google. Después de un día completo de ayer, no sé qué más hacer y luego hacer preguntas tontas con solo indicar mi problema.

• El sistema no realizará un arranque regular (sin embargo, puedo abrir un shell raíz de rescate en el que puedo montar el sistema de archivos y habilitar la red hasta cierto punto (puedo acceder a redes externas pero no puedo abrir el puerto 22 o iniciar un deamon ssh – Sin embargo, puedo iniciar apache y abrir el puerto 80)
• No puedo instalar ni eliminar software, ya que dpkg siempre se queja de las imágenes de encabezado de linux antiguas (creo que un administrador anterior eliminó manualmente los encabezados de linux de la partición de inicio para hacer espacio).
• Ahora, cada vez que trato de hacer apt-get instalar o eliminar o actualizar, o lo que sea, se queja de que había demasiados errores en dkpg y, especialmente, donde había errores con algunas imágenes antiguas de Linux (que no están presentes en mi partición de arranque) y se anula . También se queja de no encontrar archivos (relacionados con los encabezados de linux anteriores)
• Encontré una instrucción que sugería reinstalar grub2 que seguí. Creo que la eliminación funcionó pero la instalación se interrumpió de la misma manera que no se puede instalar otro software. Confío en que la próxima vez que reinicie la máquina no podré ingresar a un sistema de rescate porque parece que se ha desinstalado grub2.
• No puedo hacer algo como apt-get install linux-image-generic

Entiendo que esta publicación no incluye una pregunta adecuada, pero ni siquiera sé cómo formularla. Parece que hay tantas cosas rotas que obviamente perdí la pista de dónde empezar.

editar

salida de dpkg --get-selections : http://pastebin.com/CRFaaJ7m

salida de apt-get install linux-generic : http://pastebin.com/7t20Bavu

salida de dpgk --configure -a : http://pastebin.com/Hpmch9dM

También creo que la salida podría ser interesante (especialmente a partir de la línea 484): http://pastebin.com/uUi86FtT