Android is open source and Google play services is technically possible to avoid. What other major operating system vendor for consumer electronics goes out of their way to make this sort of thing possible? Apple and Microsoft sure don't.
Legally or illegally? If you don't care about doing it legally, sure you can make a stub Google play service and fake the device integrity by extracting certificates from other devices.
If you care about the laws though you cannot really get rid of the play services.
What’s illegal about stubs + extracting certs?
If the certificates were used for copy protection, the DMCA might apply. If they weren’t part of the API, copyright might apply. Patent law doesn’t apply, and trade secrets don’t enjoy legal protection.
They could argue you’re in violation of their terms of service, but their remedy for that is to kick you off the services you’re actively avoiding.
Is there some other law I’m missing?
The stubs still need to use Google servers for FCM but without following their terms, is that okay? Probably a grey area at best.
Extracting the certificates used for protection is against the DMCA in the US and probably legal in the EU as part of the interoperability exceptions.
If you read the article I linked and many of the criticisms in these comments (not to mention TFA) smartphone vendors need to cede a huge amount of control to Google to have a viable product. As such, the open source aspect of Android is just a very effective distraction from the anti-competitive practices that Google has been plying with it.