I just read the thread because I was interested in removing Google stuff from my Android too. Well, it really seems to be impossible to fully remove Google because - Android is Google.
But I was a little shocked about the people here saying like "It's a Google OS so it's of course sending our data to Google. Other OSs do that too." That's right, but I was wondering - Wouldn't the idea of an
independent phone OS be better? Why do we have to transmit our - in some cases sensitive - data if we want a phone that is able to run apps? We can at this time only decide between having an OS being able to run apps you want but sending your data to big servers located anywhere abroad and having a phone only be able to place calls and send SMS but respects our privacy. You're not even realizing that these companies are growing bigger and more uncontrollable through what's going on at the moment. The problem is just that nobody cares about what their phones send in the background. I think the OP is right with his doubts about Google.
In times where your private messages can be
sniffed,
the NSA has an eye on you if you don't want to share data with them, where we're storing data where anyone can theoretically access them and
AOL publishes what every single person is searching for it's always better to think about privacy. Imagine the Holocaust repeated, and "they" would just have to access Facebook's Graph search to find out who'd be a jew, and for those who are not publishing it on Facebook they could find a way to find it out anyways. Just to give an example why all this internet storing stuff could end really bad.
I decided to make a tutorial as far as I can help. I'll seperate it to root and non-root operations you can do to remove Google content and increase the security of your data (I know the increasing security part is off-topic, but I'll add them because I think who reads this topic is interested in data security anyways).
I don't know if all of the steps are really helping. If you tell me more stuff to add it'd be great as we then have a mostly complete list of what you can do. Hence this list is
not complete but should help the one or other anyways.
I've also posted - in my opinion reliable - alternatives for Google's apps at the bottom.
1.: Stuff unrooted users are also able to do to decrease data sent to Google (aswell as rooted, of course)
- Disable Google's components
I don't really think this will change much, but the more the better.
Go to your device's settings and head to the application manager. There you can deactivate as much Google Apps as you want - best would be all that are able to be deactivated. Some apps may require "uninstall updates" before deactivating.
If you have any Google application from the Play Store (or anywhere else) and these were not pre-installed you can also fully uninstall them.
- Delete your Google account.
Not just from the phone, I mean really deleting it unless you don't need it e. g. for work. If you really want to unbind yourself from Google this is an important step. You can disable your account here. As Google will not fully delete your data stored at them anyways, it may help to delete everything manually first, like Google Drive content for example
- Disable extra Google content where possible
There's some stuff more left which you possibly can disable too. However, some might not be needed to be disabled anymore if you removed your Google account. The paths may vary in different Android versions. I'm using Android 4.4.4 and will post these steps how my phone displays them.
Device Settings -> Location: Disable Google Location Reporting
(Sorry - I haven't found more, but I'll add stuff here if you know something else)
2.: Stuff only rooted users are able to do to decrease data sent to Google
- Uninstall Google Apps
(Not needed if you're going to do the next point and going to install CM)
All of them.
To do so, take your favorite root browser (for those who have no: Just search for one. Some need to have the root function enabled manually) and go to your root directory ("/"). Then open System ("/system") and head to App ("/system/app") folder. There your stock-installed apps are listed. Delete the *.apk's listed below. It's easier with this
Google Apps list (Can't promise it's complete, that are all I found) (That they're listed here doesn't mean these are all installed on your phone; this varies. Delete any apk from these you see in your /system/app folder):
Books.apk
CalenderGoogle.apk
Chrome.apk
ChromeBookmarksSyncAdapter.apk
ChromeBeta.apk
CloudPrint2.apk
Drive.apk
GenieWidget.apk
Gmail2.apk
GoogleCamera.apk
GoogleContactsSyncAdapter.apk
GoogleEars.apk
GoogleEarth.apk
GoogleHome.apk
GoogleTTS.apk
Hangouts.apk
iWnnIME.apk
iWnnIME_Kbd_White.apk
Keep.apk
LatinImeGoogle.apk
Magazines.apk
Maps.apk
Music2.apk
PlayGames.apk
PlusOne.apk
QuickOffice.apk
Street.apk
SunBeam.apk
Videos.apk
YouTube.apk
- Flash CyanogenMod or another stock android rom without GAPPS
CyanogenMod is a stock android ROM which is available for many devices. It supports all functions your phone needs and is - as far as I know - the most pure stock Android ROM. It doesn't have any bloatware, spyware or Google Apps preinstalled (except the usual Google stuff)
I won't explain how to flash CyanogenMod on your phone as this probably varies for every phone. You can find installing tutorials for your phone in the internet. The basic steps are: Nandroid backup - Flash a custom recovery - Flash CM
After flashing, don't install GAPPS of course.
- Don't use Google nor its products
Google will collect some data anyways if you continue to use it with your phone. Alternatives are given at the bottom, too. The same is for their products like YouTube and so on.
3.: Stuff you can do to protect your privacy even more, not specifically for Google
- Orbot + Orweb
Orbot is an application which allows you to extremely anonymize your internet traffic. It's more than just a proxy, it "uses Tor to encrypt your Internet traffic and then hides it by bouncing through a series of computers around the world."
It's not just encrypting your traffic, it also makes you able to visit specific websites e. g. not available in your country. For me (I'm from Germany) for example it makes me able to use the Pandora app. For non-rooted users it can only work for apps which have a proxy function like Twitter or Firefox, for rooted users it works for any app they choose or the whole system.
Tutorial
Orweb is the matching browser for Orbot. It makes you able to browse anonymously. It will not leave website data like web history stored on your device and even gives you access to .onion URLs.
- PryFi
To say it shortly, PryFi protects your phone from being reported to stores which buy systems that make them able to track customers' MAC addresses. It can even "confuse" those systems by randomly changing the MAC often.
More information about it you can see in the linked XDA topic, aswell as the download.
- Antivirus apps
There are many antivirus apps you can use to protect your phone even better from apps sniffing your data, for example. It's, aswell as on PCs, always recommended to have one installed.
4.: Alternatives for Google's Services
To keep it short (this post is already lomng as hell anyways lol), I'll only add alternatives for Google services you can't "easily" find an alternative for. There are bunches of alternatives for example for Google Camera, Play Kiosk or Play Music.
Chrome: Orweb (see above) / Opera / Firefox / Dolphin / Safari (not Apple's) / ...
Play Store: Amazon App Store / 1Mobile / AppBrain
YouTube: I don't really think there's an alternative for YouTube itself, but you can install an alternative app or visit YouTube from your favorite mobile broswer anonymously
GMail: You can login to your Gmail account from any universal email app you like
Google Search: I suggest you to use a non-tracking search engine like DuckDuckGo or Startpage
Google Drive/Photos: Any online cloud such as Dropbox. I'm not sure if these are treating your data more safely but it helps getting rid of Google.
Google+/Hangouts: I think the alternatives are clear here but you can access them from your browser if you really need to continue using them for some reason.
Google Voice Search/input: I think this app is a good alternative
Google Now: Unfortunately, I don't think there's an comparable alternative :-\
Backing up your Contacts like Google Contacts does: This app should do so well
Chrome alternative for desktop pc users (exactly like gChrome, just without Google stuff): SRWare Iron
However, I know this is a long post and I'm sorry if it's not 100% complete, but these first steps of getting rid of Google (although you'll never fully get rid of Google's stuff with an Android) should help the one or other for now.
If there are any slips in the grammar I'm sorry, I'm not a native English speaker and I'm trying to type the best English I've learned 
As I already said, if you know anything to add to here I'll add this, so we have a more or less complete list for those who want to get rid of Google at least a bit. Anyways, if you're actually hating Google or something and don't want to have Google receiving (sensitive) data from and about you you won't get around buying another smartphone anyways 
Thanks to all who wrote something yet, this makes it clearer what's possible to do so far 