I had exactly the same problem and i have found the solution.
If you follow the documentation found here:
https://developers.google.com/identity/sign-in/android/start-integrating
The first step tells you to create the configuration file (which creates an OAuth 2.0 client ID for you and inserts it into the google-services.json)
Then later, it says again about creating a OAuth 2.0 client ID, but this time it says that you have to do it for Web application
And this is the confusing part! (at least for me) because i was just taking the client id created for the android OAuth and not creating a new one for Web application (I thought the documentation was just redundant or something)
As it says, it is this one, and only this one the one you have to use as a parameter of the methods requestIdToken or requestServerAuthCode.
Forget about using the Android OAuth ID in this methods because then you will get all the time the ugly status code response 12501.
I think the main problem is that the documentation is a bit confusing about this. Or maybe because it is a bit strange the fact that you have to create two OAuth IDs.
So as a summary, you need TWO OAuth IDs, one for android and one for web application, and you have to set each one in the correct place.