Telegram's client is FLOSS. Get it on f-droid. Telegram has always had its own push service, so it works with out microg or google services installed.

The telegram service itself is non-free, but it can be used with only free software