Creo que hablamos de dos cosas distintas con la palabra "servidor". Me refiero a tu propio servidor como ahora, y para la app es transparente si la base de datos es Firebase database o un MySQL que te instales o cualquier otra.
En ese caso un usuario se comunica por HTTP con tu servidor y tu servidor manda la notificación con FCM al otro usuario.
Hacerlo sin servidor usando únicamente los servicios de Firebase no lo termino de ver.