Did some research and here are your options:
- use custom mod (the new restriction only applies to certified devices). You can use microG (/e/, iode, Lineage) or sandboxing (GrapheneOS) to run apps requiring Google services. Google will still try to kill it but my bet is it will still work for at least a couple of years
- Ubuntu Touch - you can buy new devices with it, it can run android apps using waydroid but you will not be able to run any apps requiring google services. It can run native Linux apps. Native UT apps are build using QML. It has a completely new system API so it's closer to Android then native Linux. It's based on Halium which uses the kernel from Android
- PostmarketOS - native Linux running native Linux apps. Can use waydroid. Few supported devices but everything works on PinePhone Pro and few others phones.
- Droidian or similiar - Debian running on Halium. Kind of half way between PostmarketOS and Ubunut Touch. Native Linux but running on Android based kernel
Personally, I will stick with GrapheneOS for now (my Pixel still has at least 6 years of support). When I'm unable to run all the apps I need on it I will switch to two phones setup: stock Android for work/car apps, some Linux phone for everything else. When my Pixel dies I will switch to iPhone.