A small addition to already mentioned stuff. There are multiple ways to deliver the notifications without google services. 1st and older one is by simply letting the app hang in the background indefinitely and ping the necessary servers from time to time, that one almost always works, since app developers can't really rely on gapps being installed; 2nd is UnifiedPush (that's already mentioned sunup [mozilla], but also ntfy [ntfy], nextpush [nextcloud], gCompat-UP [google firebase], NoProvider2Push [fully local]). AFAIK, it works similarly to the way gapps send notifications and uses less battery, but not all apps support it, so you may need to search for forks. For example, the official and, iirc, Foss telegram clients don't, but mercury, nagram{,x} and momo do.