Android - Android OS without Google Services?

Most after-market ROMs ship without Google Apps by default. Take a look at e.g. CyanogenMod, which is available for many devices. So if you can install custom ROMs, that's one way to go.

A different approach would be disabling all Google apps, or even remove them (on a rooted device). This might be a little more tricky as you would have to figure out all dependencies yourself.