The tricky part is people have to be willing to pay for the plumbing in this case. I think that paradigm shift can take place, but we have to show them why it's worth it first, which is difficult due to network effects.
Google could setup a domain and simply provide people freely with "[usersPublicKey].domain" subdomains updated by users with a dynamic dns client. Even if this were a google special DNS service not part of the global DNS this could work.
Google could also then provide a messaging app to use this service but if some other open source app were to become the defacto and make facebook irrelevant that is still a big win for google. Advertising $$ with one less big competitor.
If Google marketed this correctly then they could be seen as a champion of privacy too.
