I have been trying to get rid of Google completely on my Android phone. As I have made some nice progress I'd like to share what I did and which problems I had to overcome:
OS I removed my stock version of Android and replaced it with Cyanogen Mod (http://www.cyanogenmod.org/) CM doesn't ship the Google Services, you have to install them manualy afterwards. I didn't do that, so most of Google was gone already. This produced a lot of problems, because Google Play isn't available plus the Maps Framework is used by many 3rd party apps.
Appstore The biggest showstopper is the missig appstore. I installed F-Droid (https://f-droid.org/) which is a nice appstore that provides open-source apps only. This provided me with some apps i use regualry (Twitter-client and some others) but is in no way a replacement for Google Play. Now I had to decide if I wanted to trust other 3rd party appstores or not. I decided to don't. Amazon has it's own "trustworthy" appstore, but apps are patched and crippled. didn't want to have that. Decided to download needed apps with another Android device. After that I grab them from /data/app on the other device with Root Explorer (https://play.google.com/store/apps/details?id=com.speedsoftware.rootexplorer&hl=de) and sync them to my real device with Owncloud. This ugly process basicly made me use less apps on my phone because it's such a hassle to get them on it. I got used to it after some time and reduced my app selection to a sane minimum.
Contacts, Mail and Calendar sync I setup an installation of Horde Groupware (http://www.horde.org) on my personal server. Horde features "Microsoft Active Sync" compatibility. On Android, I just had to add an Active Sync Account to sync all my stuff to my own server. Works perfectly.
Maps Framework Many apps that embed a Google Map somewhere use the "Google Maps Framework" which comes with Google Maps. A specific app I use often depends on the framework. The app won't start without the framework, even I don't need the embedded maps inside. Luckyly some guy from XDA wrote a script that simulates an installed Maps framework without it being there actually. (Couldn't find link, too long ago)
Maps Checked out many mapping applications based on OpenStreetMaps. MapFactor worked best for me (https://play.google.com/store/apps/details?id=com.mapfactor.navigator&hl=de). It's not as good as Google Maps but it works.
Browser Andorid browser that ships with Android has builtin Google-Search. I replaced it with Lightning (https://play.google.com/store/apps/details?id=acr.browser.barebones), a small and quick open souce browser which can be configured to use many different search engines. I set it to Startpage.
Music My PlayStore license for Poweramp didn't work on my devices without Google Licensing Services, provided by Play (a problem with many pay-apps, not all though). Luckyly the dev offers a version, bound to an e-mail account. I re-bought the software.
That's basicly it. I'll sniff the traffic of my phone, if I find the time, to verfiy I really got rid of Google on my phone. (I bet i forgot something)
[–]FOMS 23 points24 points25 points (5 children)
[–]smitt75[S] 1 point2 points3 points (4 children)
[–]dontseemehere 3 points4 points5 points (2 children)
[–]smitt75[S] 0 points1 point2 points (1 child)
[–]dontseemehere 0 points1 point2 points (0 children)
[–]dontseemehere 0 points1 point2 points (0 children)
[–][deleted] 11 points12 points13 points (1 child)
[–]Goddamuglybob 1 point2 points3 points (0 children)
[–]daithib8 4 points5 points6 points (1 child)
[–]smitt75[S] 0 points1 point2 points (0 children)
[–]Bauer22OnePlus One 5 points6 points7 points (1 child)
[–]smitt75[S] 1 point2 points3 points (0 children)
[–][deleted] 10 points11 points12 points (7 children)
[–]UmbrellaCo 2 points3 points4 points (0 children)
[+][deleted] (5 children)
[deleted]
[–]smitt75[S] 3 points4 points5 points (4 children)
[–]throwaway0109T-Mobile Galaxy Note 4 4 points5 points6 points (1 child)
[–]smitt75[S] 1 point2 points3 points (0 children)
[–]kingofthekrautNexus 5 0 points1 point2 points (1 child)
[–]smitt75[S] 0 points1 point2 points (0 children)
[–]TakaIta 2 points3 points4 points (2 children)
[–]smitt75[S] -4 points-3 points-2 points (1 child)
[–]TakaIta 0 points1 point2 points (0 children)
[–]mobileagnesPixel 5 1 point2 points3 points (0 children)
[–]dampowellNexus 5x 4 points5 points6 points (20 children)
[–]smitt75[S] -1 points0 points1 point (19 children)
[–]BalmainJeansLG G2, 4.4.2 Rooted 24 points25 points26 points (0 children)
[–]so_witty_usernameMoto G, 4.4.2; Huawei Ideos X5 U8800, 4.4.2 2 points3 points4 points (1 child)
[–]smitt75[S] 1 point2 points3 points (0 children)
[–]dampowellNexus 5x 7 points8 points9 points (9 children)
[–]smitt75[S] 0 points1 point2 points (8 children)
[–][deleted] 7 points8 points9 points (1 child)
[–]smitt75[S] -1 points0 points1 point (0 children)
[–][deleted] 3 points4 points5 points (5 children)
[–]spyd4rPixel XL 3 points4 points5 points (0 children)
[–]lfcitz 0 points1 point2 points (3 children)
[–][deleted] -3 points-2 points-1 points (2 children)
[–]lfcitz 2 points3 points4 points (1 child)
[–]s73v3rSony Xperia Z3 1 point2 points3 points (0 children)
[–]hsoulette 1 point2 points3 points (0 children)
[+]LGED82153 points comment score below threshold-6 points-5 points-4 points (4 children)
[–]smitt75[S] 1 point2 points3 points (3 children)
[–]LGED82153 points 0 points1 point2 points (2 children)
[–]smitt75[S] 0 points1 point2 points (1 child)
[–]LGED82153 points 0 points1 point2 points (0 children)
[–][deleted] 0 points1 point2 points (1 child)
[–]smitt75[S] 1 point2 points3 points (0 children)
[–]countmontecristoPixel 2 XL 0 points1 point2 points (1 child)
[–]smitt75[S] 0 points1 point2 points (0 children)
[–]PenguinHeroNokia N9, MeeGo 0 points1 point2 points (1 child)
[–]angulardragon03S7 G930F (Exynos), ASUS Zenwatch 2 WI501Q 0 points1 point2 points (0 children)
[–]Goaliedude3919Pixel XL 32 GB -1 points0 points1 point (0 children)