Você pode usar um chroot de um live cd para instalar um pacote de um sistema de rede não-inicializável / sem rede. Seguir este guia até o sexto passo (faça o passo seis, mas NÃO 7). Eu sei que o guia é para criar grub, mas o processo chroot é o que nos interessa.
Depois de ter feito isso, você deve ser capaz de fazer apenas um sudo apt-get install dnsmasq
e reinicie.