It doesn't have to be side effect free, it just has to run in an execution environment that cannot exfiltrate data.
Make it into a special kind of "content script", that gets a blank javascript environment that does not have any of of the usual means to communicate with the outside world (no XHR, no access to any DOM, no access to any message passing, and so on).
E.g. a browser could have a special kind of "content blocker" script environment that gets fed request objects by the browser. The script can then examine all the data in the request object (the requested URL, the headers, etc) and make a decision to DENY or ALLOW and communicate this decision back to the browser in a single well-define way, and that's the only communication to the outside world it is allowed to do. No way for it to exfiltrate data. Extensions can be allowed to pass data into the environment via some form of uni-directional message passing, e.g. to update filter rules, but the content script cannot respond (and thus cannot exfiltrate data in a response).
Browsers already define different execution environments with different APIs available in them for different purposes, e.g. you have the same-origin limited environments for websites that feature Web APIs such as DOM and XHR, and those environments come in different flavors (no access to certain APIs such as the location API if you're not "secure"), Proxy-Auto-Configuration (PAC) scripts have yet another environment, extension scripts get yet another environment, extension content scripts yet another, internal browser pages such as the settings pages of browsers often get environments with access to some privileged APIs etc. To define a few more specialized environments for privacy-sensitive stuff shouldn't be too hard.