I'm not OP but I've been an Android user since the release of the T-Mobile G1 and have been trying to get rid of Google stuff for a while:
> All android devices?
No, not all Android devices. Only the ones with the Google Services Framework installed (or, if you're as paranoid as I am, any other Google service that is running as root).
To give you an overview, Google's power over Android users basically rests on the following pillars:
1. Google Services Framework (GSF): AFAIK every Google app requires the GSF to be installed on your phone these days. The GSF runs as root, includes all kinds of analytics libraries. It also links your phone to your account if you decide to set it up on your phone (which, theoretically, you don't have to but, in practice, you are often forced to). If you indeed do that and connect your phone to your account, things like contacts, calendar entries and so on get synchronized automatically.
Even worse, there's also a way for the GSF to back up all your apps' data and upload them to the Google servers. I'm just mentioning this to make it clear that the GSF really has access to everything on your phone.
Solution: Use MicroG (https://microg.org) as a GSF replacement. This, in turn, requires using a custom ROM like LineageOS and, thus, your phone's bootloader to be unlockable. Not all Google apps will work with MicroG but most do in my experience (see below).
2. Google Play Store: Most apps are only available on the Play Store, so if you want to use any of these you'll have to use the Play Store in one way or another. The Play Store, however, needs the Google Services Framework. And even if you got rid of the GSF and replaced it with MicroG (see 1), you would still have to install the Play Store as a system app, giving it root access to your phone.
Solution: Apart from getting rid of the GSF (see 1), use F-Droid for open-source apps and something like Yalp Store (or the Aurora fork) to download apps from the Play Store. (There are also ways to download apps from the Play Store using F-Droid, see e.g. https://github.com/NoMore201/playmaker) You won't be able to obtain paid apps this way, though. (Or, more precisely, you won't be able to download apps that you haven't already paid for.)
2. In-app payments ("Android Pay")
As you might expect, these are also tied to the Play Store and the GSF.
Solution: I haven't tried this in a long time but you might be able replace the GSF with MicroG and just have the Play Store installed and tied to your Google account in order for in-app payments to work. No guarantees, though.
3. Google SafetyNet (part of GSF, as well)
From my POV, this is the most painful Google "feature". It's a Google library that apps like Netflix and online banking apps use to verify that the device they're running on has not been "tampered" with. (What "tampered" means exactly is unclear -- it definitely includes rooted devices but the precise definition is Google's secret.)
If you want to use apps like Netflix, there is no real way around SafetyNet. This is because, if installed on your phone, SafetyNet will download a binary blob from Google, execute it and send its output (basically all the information the blob collected about your phone) to the Google servers. The latter will then do the verification process and notify the Netflix servers (or your bank's servers) about the result. The Netflix servers can then tell the Netflix app on your phone to lock you out if need be.
Solution: While MicroG can't circumvent this, it does support SafetyNet these days by emulating the original SafetyNet implementation. So it, too, will download the binary blob and execute it.
Put differently, in order to use Netflix and most online banking apps you will still have to make sure that your phone passes the SafetyNet test. Here, you've got two options:
Option a): Hide root access and other system modifications (like Xposed) from SafetyNet by using something like Magisk (https://forum.xda-developers.com/apps/magisk/official-magisk...).
Option b): Don't use root or any of those modifications in the first place. (I.e. you could just run LineageOS without root and you should be fine.) The problem with non-rooted devices is that they also don't allow you to run a firewall or apps like Xprivacy for more fine-grained privacy control. (When it comes to firewalls not requiring root, NetGuard does come close, though. However, it should be noted that you won't be able to use VPNs anymore.)
4. Google services that are tied a Google account, e.g. Gmail, Drive, Maps, Picasa, Home, Google Now/voice assistant etc.
As already mentioned, they all require the GSF to be installed on your phone.
Solution: I would recommend staying away from them but if you really need them you should be able to replace the GSF with MicroG and they should still work. There might be exceptions, though, depending on how deeply they are integrated with your phone. (The voice assistant might be one such example.)
5. Google services that are not tied to a Google account, e.g. Maps
Solution: Same as 4) and/or use an OpenStreetMaps-based app like OsmAnd as a replacement for maps.