OK ... well, I found at least how to use dnscrypt-proxy.
First, disable dnsmasq ...
> sudo gedit /etc/NetworkManager/NetworkManager.conf
and comment out the line which says:
so change it to:
Now go to NetworkManager > Edit Connections, click your connection then "Edit" and click on "IP4 settings" tab. Select "Automatic (DHCP) addresses only". In the same dialog, set your DNS server to 127.0.0.2
> sudo restart network-manager
Now start your dnscrypt-proxy:
> sudo dnscrypt-proxy -a 127.0.0.2 -t 53
And you are good to go.
So to make the latter permanent, make sure the dnscrypt.conf script in /etc/init looks as follows:
After a reboot dnscrypt should work fine.
description "dnscrypt startup script"
start on (local-filesystems and started dbus and stopped udevtrigger)
stop on runlevel 
exec /usr/sbin/dnscrypt-proxy -a 127.0.0.2 -t 53
I tried it also together with dnsmasq but for some reason it is horrendously slow !
I don't care so much about dnsmasq so the above will work without it.
Tested on Ubuntu 12.04.