I built AOSP from source. It's supposed to be devoid of any google specific requirements. I went out of my way to block as many google servers as I could in the hosts file just to ensure it wasn't phoning home.

As far as I can tell the only issue I ran into was that despite being connected to a working wireless access point, the device reported I had no internet. It still worked, but it seems for the purposes of the status bar icon, and whatever other underlying system code, it was using a google server to verify internet was working.

I would just stay far away from android if you value your privacy, and probably tech all together.