I haven't run stock Android in a while (and instead just CyanogenMod), but I'm pretty sure that it's not actually required, i.e. you can skip account creation during setup and then install alternative app stores like F-Droid, Aptoide or Amazon.
If we include CyanogenMod or other ROMs, then it's definitely possible, though. I do own and use an Android phone and deleted my Google-account probably half a year ago...
One of the great things about Cyanogen is maintaining tight control even over Google's apps and how much they track me.
Are you sure? How much is Play Services tracking you?
I run MicroG on my own phone, personally. It's a FOSS implementation of (most of) the Play Services APIs.
Unless you are using some sort of VPN or proxy that's constantly changing your IP as you're browsing, and a browser that consistently changes or masks fingerprintable information and wipes all persistent tracking beacons, then what you're doing is not even remotely sufficient to evade tracking by any entity. What you're doing is definitely not enough to avoid Google or Facebook.
At this time I believe nothing can do this with 100% effectiveness. The closest would be to use Tor Browser and never disable NoScript and only use sites that don't rely on JS... but even then there are many theoretical workarounds, many more to come in the future, and probably various unknown techniques currently being tested or deployed.
I know enough about the technology to realize it saves me a lot of time, effort, and stress to just accept my fate. I no longer include ad networks or big tech companies in my personal threat model, even though I dislike what they're doing.
That's the reasoning I came to as well, I'm fine with certain sites using JS, session data and filling up my .cache if it's convenient.
The more I understand my fingerprint on the web the less paranoid I get. Lots of comments here advising not storing anything, or using anything... they may as well use tails as their main OS or throw out their computers entirely.
The same privacy-intense users lose credibility when they advice people to trust a bunch of add-ons instead of using system-wide blocklists in their host file or strict IDS rulesets.
On the comparatively rare occasions when I need more privacy, I do more. For instance, I tend to use Tor if I'm staying at a hotel that ties the WiFi connection to you personally - I think those connections are as bad as it gets for privacy.
1. Google account - I have one because it's required for Android, but I have never used Gmail, do not search from my Google account or ever log into it from my browser.
2. Facebook or any subsidiaries - never.
3. General Web browsing - reject 3rd party cookies automatically, browse with uBlock Origin, disabled JavaScript (via ScriptSafe) with selective enabling of scripts, Privacy Badger.
4. Only enter my real name online for things I explicitly need/want associated with me. Only enter my real address if actually needed for a delivery or other reason.
5. My mail client is set not to load remote images, which protects me from those 1x1 tracking images.
Many of these make the Internet a better experience, and certainly protect my privacy to a large degree. Yes, corporations have some data on me, but not much, and it's not all correct. I also don't feel I'm missing out on too much cool tech stuff, a lot of the privacy-unfriendly stuff is entirely unnecessary, for me at least, or replaced by alternatives that are not much worse.