Hey so it turns out that the android apps were using my IPv6 DNS, so I disabled DHCPv6 with
/etc/init.d/odhcpd disable
/etc/init.d/odhcpd stop
and the ads stopped appearing from the apps as well!
It's honestly very odd how the DHCPv6 gets mentioned very seldomly in this kind of problems, I noticed it only when I switched to another phone, since on my samsung the IPv6 DNS doesn't even get displayed. I partially found the solution from this post
but was sheer luck that I noticed the IPv6 DNS on my other phone and thought it might have had something to do with it. Anyways, thanks everyone for the help!