I really doubt Google is going to play chicken about something so serious as giving away all their user data. Is it incomprehensible to you that they are telling the truth?
So from a PR perspective I don't see how Google can fix this unless US law substantially changes (or they employ crypto on the users side but that undermines the economics of much of their business).
[1] I'm not convinced that it is legal under EU data protection law and Google does have a presence in the EU, but I'm no lawyer.
This is true, at least in Google's situation. However I think there is an untapped market of people that want to be advertised to, provided the advertising is relevant.
Surprisingly I think traditional print magazines actually have this figured out. The advertisements for designer clothing, watches, and booze get a lot of readership in "gentleman/bachelor/whatever" magazines (not sure what the correct term there is, not trying to refer to porn (well, except Playboy)) and I suspect that removing them would actually damage their subscription rates. Now, these adverts obviously are not targeted to the individual, but I think they nevertheless demonstrate the concept.
I'm sorry but where are you getting this from? Google has categorically stated that they do not share data without court approved mandates. There is no mass "targeting" that is going on, no matter what the nationality.