At the OS level LineageOS offers per-app network permissions, which I've used and functions as expected.

One quirk from what I understand of this ticket[1] is if there's a proxy set up via a separate internet allowed app it can bypass the restriction via that app. GrapheneOS' implementation is said to prevent this.

[1] https://gitlab.com/LineageOS/issues/android/-/issues/3228

There's RethinkDNS [1](not affiliated to them, just like their software). Sometimes it gets killed on my phone, but otherwise it's a great replacement, adds some much-needed features like proxies and wireguard VPNs on top of a DNS and app level control.

[1] - https://f-droid.org/packages/com.celzero.bravedns/

No, if you have a rooted phone you can use AFWall+. And there are other non-root firewalls.

I've been using Blockada for many years but that's a firewall against ads and trackers. No ads inside apps.

Ideally I would use NetGuard to block the apps and Blockada to block ads and trackers for the apps that I allowed to perform network traffic in NetGuard. But Android allows only one active VPN and they can't be chained, so it's a hard choice. Actually it's not so hard: I keep blocking ads and trackers.

My favorite is another FOSS, but this one is special because it doesn't need network permissions. No root, ofc, so that sticks.

Karma Firewall https://f-droid.org/packages/net.stargw.fok/

I have used GlassWire (not affiliated) for a few years without issues.

It's also rootless so I assume it has the same restrictions, but it's been very helpful with apps like Uber, which I use seldomly, but prefer not to have their notifications shoved in my face every 30 minutes.

It's also helpful for disabling access to most of the bloatware that comes with e.g. Samsung phones and such.

Probably not blocking everything, but I feel like it's at least something.