Why make this so difficult? Just ban personally targeted advertising. That's what everyone is really trying to achieve. Nobody really cares about any individual's personal data beyond using it to try to sell him something. Ban using it for advertising and it becomes worth less than the cost of collecting and storing it.
Sites can just go back to content-based targeting for ads.
Sites can just go back to content-based targeting for ads.