Do they really need advertisers? I'm not sure why all these companies think the whatsapp route isn't possible. People are happy to pay a small yearly subscription for apps if they're truly doing something useful. While I don't personally use telegram, I'd argue it falls into the category of "useful enough to pay for".
Telegram has many nerdy hobby communities which could buy the cosmetics or whatever and subsidise the service for the normal users.