They could anonymise their search data before storing, so that they don't store individual actions, just something like group preferences to tailor searches and target advertising. This wouldn't be easy while keeping their advertisers happy, but it's an interesting problem - how do you tailor search and advertising while not keeping track of every URL the user searches or clicks on. It would be interesting to know if turning off google web history actually turns anything off apart from the UI to display this tracking to the user - they have a disclaimer saying they still log for other purposes even with web history turned off. They could allow users to turn off this tracking completely.
They could make gmail delete old mails after 1 year or so by default, as a security measure. Keeping everything forever on a server is not a great idea if various governments are then given access to that data at some point in the future, and people should keep their archives of mail locally, not on Google's server - Google should encourage that.
They could offer easy to set up encryption on gmail, in fact they could set it up by default for each user. If the user chose to this could kick in automatically when emailing any account on their own service, giving a lot of people encrypted email all of a sudden without any effort on their part. That would make a vast number of email communications encrypted, and coupled with deleting older emails, this would make it far harder for the NSA to snoop on email communications, at least for those who don't use webmail and delete their old messages from the server. If Google did this and used an open standard, other providers like Apple, Hotmail etc would follow, and mail readers like Apple mail would be changed to read the messages.
Finally, they could do far more to explain what they are gathering on each individual, and in what circumstances they will pass the material on to the NSA - they claim that they robustly defend the rights of their users, but without actual proof, this is not very convincing. I read their lawyer's Q&A with the guardian last week, and nothing of substance was said, though lots of vague denials were included again:
"We review each of those requests and push back when the request is overly broad or doesn't follow the correct process. There is no free-for-all, no direct access, no indirect access, no back door, no drop box."
Which tells us nothing about what actually does happen, and whether Google has enough information to effectively oversee these requests. If they don't feel they can legally tell their customers what they are doing, they should be campaigning far more robustly and openly for the right to divulge that information, and fighting it in the open courts with ACLU now that the details have emerged. They could start by simply refusing to cooperate with FISA requests going forward, until a more transparent system is put in place - Twitter hasn't been cooperating, so why should Google?
This scandal is damaging their standing in other countries, and the best way to counter that would be to be open and honest (in spite of the secret laws they are asked to operate under) and stand up for their users' privacy with concrete actions rather than denials. If they continue to give information to the NSA, US users should be very concerned about what Google will say when all the other governments of the world require data on US persons from Google subsidiaries, following the NSA's example.