Сделал пакет
dnsmasq-caching-config, который тянет
dnsmasq и прописывает нужную строчку в его конфиг. При удалении dnsmasq-caching-config выполняется перезапуск resolvconf и network-manager, чтобы не сидеть без интернета до перезагрузки. Физику процесса можете посмотеть в скриптах установки-удаления пакета.
В описании пакета есть несколько DNS-серверов, выбор на ваш вкус, меняются через Network Manager. Запросом в терминал наподобие "dig ya.ru", если поставите пакет dnsutils (dnsmasq-caching-config его рекомендует), увидите отчет о dns-запросе. Второй и последующие запросы одного адреса будут идти с задержкой 0 мс.
Ну, а если Вам хочется динамически переключать dns - это нужен некий скрипт, думаю, upstart-задание, там есть условия запуска при подъёме сети. Вот с этим пока не помогу, скриптописатель я пока начинающий. В любом случае оперировать он должен некими заданными dns, советую попробовать яндексовские - особенно хороши для рунет-сегмента. OpenDNS - у них довольно крутая инфраструктура, но последний год они закрывают под предлогом фишинга вполне толковые сайты, поэтому - советую лишь как вторичный сервер в дополнение к какому-либо. Серверы Comodo тоже неплохо себя показывали.