My brother in Christ, if everything failed (and when I say everything I mean e v e r y s i n g l e t h i n g) it may be that the Firebase have not generated correctly the google-services.json for some reason. That was just what happened to me. Removing and re-adding the keys on Firebase will solve it.

The secret to debug any of this mess is to get your phone with the app from the PlayStore installed, connect it to your PC and logcat the stuff with something like (substitute completely <ADBDEVICENAME> and <APPNAME> including <>):

adb -s <ADBDEVICENAME> logcat | grep <APPNAME>

and then look for:

[GetTokenResponseHandler] Server returned error: Invalid key value: <SOMEHASHHERE>

is what you're looking for to see what it is being doing wrong, because in this line the logcat will spew a hash that can be converted to HEX so you can actually compare within your code if it is a debug key or if it is a key coming from the Play Console that is on Firebase but not on the google-services.json and so on.