I have to ask though, what do you mean by "app data"? Do cell carriers really have a way to figure out that apps are sending out the data, or is it just charging more for websites and such?
Are you saying that they sent all your data to their backend servers and stripped ads there?
Or is it just that they were doing it client side, but your phone company erroneously double counted data even though it wasn't sent twice over the wireless?
If you want to read of the numerous reports of the same issue, Google "adblock plus data usage android" and click on any of the forum discussions about it.
Now I just root my devices and use a hosts file (MoaAB - Mother of all Ad Blocking).
You could also run your own "localhost" DNS to block ads. This is a bit more flexible than the HOSTS file. Even if you are a novice, I believe once you have this setup working, you will never go back to third party DNS such as your ISP or openresolvers like Google, OpenDNS, etc. Just my personal opinion.
By using DNS you can also block ads across all your devices, at least on your home LAN. You use one device to block ads on all your devices by making the one device a gateway for the others. No need to root the devices; just change the gateway in network settings.
It all works beautifully. Maybe someone should do a startup? It seems like there is real demand for blocking ads and the current solutions leave much to be desired.
On the free side, I can package a working solution on a bootable USB stick, SD card, CD, etc. Or I can make it a userspace kernel, Xen kernel or some other virtualized format for the "container" enthusiasts.
Without expending any effort to reduce size of the bootable kernel the whole thing (with embedded filesystem) weighs in at about 20MB.
Enough configuration has already been done so all you have to do is come up with a spare computer (e.g., old laptop, PC), boot and enjoy the ad free experience.
You can also block google-analytics, mobile apps than phone home, etc. You can stop your Apple devices from being the beacons they are: they phone home to multiple domains constantly 24/7. Running your own DNS also makes redirections easier, e.g., when you are monitoring SSL traffic being sent from apps, etc. The list goes on.
Note I am not denigrating the HOSTS file. I regularly make use of the HOSTS file in tandem with DNS, but not to block ads.
Since AdBlockPlus uses a local 127.0.0.1 HTTP proxy if you don't have root access to modify hosts.
No way the carrier had spyware ON my device. Was running a Moto X dev edition with a Custom ROM & kernel at the time.
Google the phrase "adblock plus data usage android" and read some of the forum discussions / reports about the whole thing.
Tried out AdBlockPlus (not the browser) for a month - horrible experience. They actually firehose/stream all of the data your phone uses through their app to block the ads, so for that month my data usage doubled because most major US carriers consider "app data" as separate usage. Really, most apps available (now) on the Play store related to removing ads just really don't do it right, and sketch me out mainly because Google has taken a much more proactive approach recently to removing "real ad blockers."
So far the best solution IMO is to root your phone (necessary for this), install F-Droid, and install AdAway (which was once in the Play store). It uses the hosts file to block advertisements (the default list is great) and has worked wonderfully, without changing my experience at all (other than removing all the ads).