There are three approaches:

1. Create a browser with ad blocking builtin or possible with addons (like Firefox).

2. Create a local proxy that blocks ads, and make the user configure it as the system proxy.

3. Require root privileges and do whatever you want (2, or maybe change /etc/hosts, like AdAway does). Yes, there are tons of apps in the Play Store that only work with root. Google never cared much about them.