You can also say to your users - we have a problem with this legislation we are moving our servers to Iceland/Bermuda/Switzerland.

When the government sees it hitting their tax take they will listen

I don't think that moving servers is at all realistic option for google. I am much more worried about traffic logging at the isp than I am of what google records. However I will concede that because of the shear volume of data that google collects and retains it is a much is a worrying if they decide that it is ok for them to go dredging.

Or disclose in a big blinking disclaimer, here is what we track and here is who we are required to give it to. With full disclaimer that is readable and not legalese, I feel that it is fully ethical to provide said information to the US or Chinese government or whoever.

On the other hand, are Google required to store the data? I suspect they aren't, they only need to hand over what they do have when asked. So they could always let you opt out of them tracking your data. Which they don't. Sure, it might slightly reduce the quality of search results those users get to see, but that's a sacrifice I'd be willing to make.