and there is no workaround other than paying the cellular provider for the privilege of using your connection as they see fit.

there must be a workaround. I have been seeing solutions for this in the past, but I don't remember because I haven't had such a shitty provider.
probably it's the TTL value in the packets. if you can move the sim card or a clone of it into a portable openwrt router, that's an easy fix, otherwise it would probably need patching android which you probably can't do because graphene is too hostile to that.