Speaking of Gmail, I also want to stop using Google services. I went back the good old times, just setup a mail server on a linux dedicated box and started sharing my new email address. It's going to be painful but there's no way around it. You can then setup POP or IMAP on Android like we always did before.
I remember a discussion with a friend of mine about the source of these problems, we came up to the conclusion that Internet was an amazing technology when poeple could speak up their minds freely, this is how Internet itself was built and the same for good Open Source projects like Linux. But now we let the greedy guys run businesses with internet and they are trying to replicate the physical world. We are basically transforming what was a door to creativity and freedom to a mirror of our daily lives. And the common factor to all these problems is "identity". Most internet technologies and new startups are obsessed with identity. We are linking authentication to more social networks. Linking our phones to online services and always giving our identity in the process. I wonder what would be the Internet if there was no way to have "identity" at all supported in the protocol level. Maybe it's too late.