Is this a corporate network or a public access network, or something along those lines? I would have expected blocking everything and then using some kind of proxy server (transparent or otherwise) would be standard procedure.
If you’re using DHCP you control the DNS settings for clients already. If someone really needs a static address you can do reservations or even hand-configure a device and still specify a local DNS server.
I guess I don’t understand why a company network would even give the illusion of letting its users use external services directly.
If you’re trying to get around geofencing though, keep me away from that.