Block at DNS level on a device (router or DNS server) and proxy all Android traffic to said device.
I use a pfsense router running OpenVPN and pfblockerNG. PfblockerNG sinkholes all DNS requests to domains from a list such as this one. Then by using OpenVPN I simultaneously encrypt my connection when roaming remotely and I can specify to use my home DNS server to sinkhole ad/tracking domains.