EDIT MAY 6,2016
I've written a script to update all settings for system connections in the /etc/Network-Manager/system-connections/ directory. The GUI that you use to edit individual connections, edits a particular file in that directory. The script updates all of the files - it just searches for those who don't have dns set with grep and sets it with awk.
Since accessing those files requires sudo access, run this script with sudo and then - restart network manager
#!/bin/bash
# Author: Serg Kolo
# Date: May 6, 2015
# Description: this script checks all settings for connections in
# /etc/NetworkManager/system-connections/ , and if there's no custom
# dns set , this script sets it;
# NOTE: run sudo service network-manager restart after running this script
set -x
for file in /etc/NetworkManager/system-connections/* ; do
grep 'dns=208.67.220.220;' "$file" || ( awk '{print;if ($1=="[ipv4]"){getline; print "method=auto\ndns=208.67.220.
220;\nignore-auto-dns=true"}}' "$file" > .tmpfile && ( cat .tmpfile > "$file") )
done
Script in action:

ORIGINAL POST
Some users here pointed out that DNS is somehow controlled by dnsmasq. That is indeed true. I've faced a somewhat smaller issue, where no matter how I changed head or body in /etc/resolvconf/resolv.conf.d , my computer couldn't actually access interned by domain name - only working with IP addresses.
What I did is to edit the /etc/NetworkManager/NetworkManager.conf file. Originally, it said dns=dnsmasq but I changed it to: dns=208.67.222.222. Although this way, nm-tool doesn't mention 208.67.222.222, I still was able to use domain names, not just IP addresses.
Here's how my NetworkManager.conf file looks like now:
[main]
plugins=ifupdown,keyfile,ofono
#dns=dnsmasq
dns=208.67.222.222
[ifupdown]
managed=false
NOTE: For more details on my problem and this solution, refer to my post on askubuntu.com.
UPDATE #1
Having returned home from the university today, I discovered that I couldn't connect to my home WiFi. I've read-up a little on man NetworkManager.conf and it turns out that dns= in [main] is actually a line for plug-ins, so line dns=dnsmasq is actually adding the dnsmasq plugin to the NetworkManager, apparently.
So my solution still worked, just not as I had expected. Here's excerpt from the man page:
dns=plugin1,plugin2, ... List DNS plugin names separated by ','.
DNS plugins are used to provide local caching nameserver functionality
(which speeds up DNS queries) and to push DNS data to applications
that use it.
So by setting dns=208.67.222.222 I may have, basically, prevented NetworkManager from using that plugin, which would otherwise used the local DNS server (which apparently doesn't work).
dns=nonein/etc/NetworkManager/NetworkManager.conf(see details in my answer below). – Skippy le Grand Gourou Mar 05 '19 at 09:09