Allora per renderti la vita più facile penso che tu avessi ragione, dovresti usare le notifiche Firebase. Purtroppo non le conosco, dovrei mettermi a studiarle.
Leggo un attimo al volo il thread di Erel ma non ti prometto alcunché, serve troppo tempo.
Potresti creare un'app di prova, per notifiche generale, prima di implementare esattamente ciò che ti serve (anche se suppongo che un'app di esempio Erel l'abbia già pubblicata e probabilmente ti basterebbe usarla come base).