With the help of some linux hackers, you can now have an Android phone, that is completely free of Google's software!
For those who want a 100% free Android experience, the Replicant project offers images for a handful of devices. But this project does not appear to have a vast number of developers; releases tend to be slow (the last was 4.2 in January) and a fair amount of functionality is missing. For most users, Replicant is probably not the way to go at this time.
Instead, for most, the starting point for an alternative Android device will be a CyanogenMod release. CyanogenMod is not 100% free; in particular, it contains whatever non-free drivers and firmware are needed to make a specific device work. But, above that level, CyanogenMod is free; it is mostly a build of the Android Open Source Project (AOSP) release with a bunch of added goodies. Google's proprietary user-space apps and utilities are available, but they must be downloaded and installed separately. It seems certain that the vast majority of CyanogenMod users immediately do that installation, but it is not necessary to do so. Your editor started this experiment with a fresh CyanogenMod 11.0 M7 release without installing the Google apps.
To me this seems really cool, and might be a great excersize in learning how dependent on Google you actually are, the results maybe surprising.