To anyone serious...
Don't let them tell you it can't be done. Most Android phones in China don't have google.
I've been running ROMs since CM7 without instaling Gapps. It works just fine.
As a matter of fact, that's the easiest way to do it, if you know what you are doing. Just flash CyanogenMod and then don't flash Gapps ( Google apps ). You have to find alternatives to Play store, but they are out there. Also, if you know what you are doing, just find a friend that wants you to root his phone for him, and then if something comes out on play you really, really want get him to download it for you and send you the APK and install it that way.
The other thing you can do is, root your phone, signup to google, download all the apps you want, backup the APKs, reset and do the above. If you make backups, it's no big deal to flash back and forth to get apps from the store. Flash Gapps, download, factory reset and format, reload and go.
Then, if what you want is to be safe, get a root permissions manager and kill permissions on apps they don't need and shouldn't have.
That said... I've was just searching for more info on how to make an android phone as secure as possible and it's been fun watching people (not nessesarilly these people) on the internet that had a cow over Carrier IQ have no problem at all with the idea that Android isn't just a platform for google spyware, it actually IS google spyware.