For those of us stuck on normal android, is there a way to achieve that? I know it used to work with some firewall apps but nowdays they all require root access.
It looks like you can't revoke the internet permission, but you can use the firewall via ADB. Settings are lost on reboot, but you can use an automation with Tasker or similar to set them on boot:
Or you can set your DNS resolver to dns.adguard-dns.com and it blocks almost all ads. You can search "private dns" in Android settings app and set it there.