Ubuntu, apt-get con error disco lleno

En sistemas con poco disco disponible en alguna ocasión dan problemas de disco lleno con las actualizaciones, y si tenemos la mala suerte de que además tiene dependencias incumplidas por otro motivo, finalmente nos quedamos bloqueados porque no podemos actualizar porque no hay espacio y no nos deja liberar espacio desinstalando aplicaciones porque hay dependencias incumplidas.
Por ejemplo el siguiente mensaje:

Los siguientes paquetes tienen dependencias incumplidas:
linux-headers-x.x.x-xx-generic : Depende: linux-headers-x.x.x-xx pero no va a instalarse

Pero si intentamos solucionar las dependencias incumplidas nos encontramos que no hay espacio:

dpkg: error al procesar /var/cache/apt/archives/linux-headers-x.x.x-x_x.x.x-x.xx_all.deb (--unpack):
error al crear el directorio `./usr/src/linux-headers-x.x.x-xx/': No queda espacio en el dispositivo
No se escribió un informe «apport» porque el mensaje de error indica que el error es de disco lleno
dpkg-deb: error: el subproceso copiado se mató con la señal (Tubería rota)

Y si queremos liberar espacio desinstalando con apt-get remove, obtenemos el primer error de dependencias incumplidas.

¿Solución?

Tipicamente debemos desinstalar los kernels antiguos que ya no usan, para saber cuantos tenemos basta con hacer:

sudo dpkg --get-selections | grep linux-image

y veremos todos los kernels instalados. Tipicamente habría que dejar solo el último y uno o dos más, el resto nos sobra (y nos hace perder espacio de almacenamiento).
No podemos utilizar el "apt-get remove" porque tenemos dependencias incumplidas y no nos dejaría, así que tenemos que usar algo mas rudimentario: dpkg
Dpkg es la base del gestor de paquetes, es decir, apt trabaja por encima de él.
Por ejemplo, si al ver los kernels instalados vemos que tenemos:

linux-image-3.5.0-46-generic deinstall
linux-image-3.5.0-47-generic deinstall
linux-image-3.5.0-48-generic deinstall
linux-image-3.5.0-49-generic deinstall

Habría que desinstalarlos uno a uno, con sus dependencias:

Para el 3.5.0-46:

sudo dpkg --purge linux-headers-3.5.0-46-generic
sudo dpkg --purge linux-headers-3.5.0-46
sudo dpkg --purge linux-image-3.5.0-46-generic

Para el 3.5.0-47:

sudo dpkg --purge linux-headers-3.5.0-47-generic
sudo dpkg --purge linux-headers-3.5.0-47
sudo dpkg --purge linux-image-3.5.0-47-generic

Para el 3.5.0-48:

sudo dpkg --purge linux-headers-3.5.0-48-generic
sudo dpkg --purge linux-headers-3.5.0-48
sudo dpkg --purge linux-image-3.5.0-48-generic

y así sucesivamente....

Este liberará suficiente espacio para que podamos hacer un
sudo apt-get install -f
que solucionará el problema de dependencias incumplidas.

Fuente: Foros de ubuntu

[Actualización 06/11/2016]
He subido un script que automatiza el borrado de los cabeceras, y las lineas. Simplemente hay que pasar como parámetro la versión a borrar. Está disponible en el mi repositorio de GitHub admin-scripts