Android (at least with the standard Google services) seems to provide an implentation of this through the play integrety API [0]. I'm not familiar with the internals of that system, but I have worked on this type of system for a much more constrained use-case.
If I were designing this, my first pass at a napkin design would be:
* Devices running the app must have a TPM. This TPM is loaded with a private key that is intended to remain highly secret. Corresponding public key is well known.
* During boot, "everything" is measured into the TPM's Platform Configuration Registers (PCRs). To measure something into a PCR, you update the PCR value as: PCR[n] = hash(PCR[n] || measured_value).
* The TPM does not (in this use-case) have a notion of what the "correct" values of the PCRs are. However, it can use the secret key to sign the PCRs values. Forging this signature would require either breaking the underlying crypto, hacking the TPM, or learning the secret key contained within the TPM. To prevent replay attacks, the TPM includes a nonce sent by the server.
* The device sends the server a list of what firmware/kernel/OS it is running (everything that was measured into the TPM). The server determines what the PCR values for the claimed configuration should be, and validates the signature that the TPM generated
* You now know that the OS is "trusted", and can now trust the OS to verify that the app is signed by a given public certificate and is running in a sufficiently secure environment.
Redirect_uri helps with webapps that run on a standard web browser. However, if the client is not a web app (or, is running under a properly modified web browser), it can simply ignore the redirect.
Oauth2 does contemplate a client_secret field for client authentication. However, such a field is useless on public clients.
The oath2 spec is very explicit that client_id can not be used as a means of authenticating clients.
The fact that without the associated secret, an API key is useless.