On Android there is NetGuard which poses as a (local, running on the phone) VPN and allows you to deny / allow traffic based on process and domain. Works great, no root needed.
Then you can't run another VPN right? Then raw through Verizon with their tracking headers and stuff for anything non-https unless you go through the series of opt outs that get periodically invalidated with a new opt out needed.
Just checked, there doesn't seem to be an option for it (though technically it should be possible, I think). Sorry to hear about Verizon - hopefully mobile will soon be a viable option for you. Good luck!
I agree that there should be an app firewall to the point I’m running an older phone w the checkm8 jailbreak to have a firewall.