I recently discovered nogapps, and it’s working great! Here’s an intro and how to use it.
#
Background
When installing Android on a phone, one first flashes the ROM, i.e. Cyanogenmod. Then a package called gapps, which contains Googles proprietary Apps. This is necessary to get Play, Youtube, GMail, Maps, etc. And lots of apps from Play requires Play and it’s services to function.
See also Androids privacy invasiveness and Android with as little closed source as possible.

