Impossible? No
So, let's look at how this could be done.
First, a principle of security is not to rely on 'security by obscurity'. Every detail of the scheme must be open to peer review. The only secrets are keys. Obviously the scheme will have to be opt-in for manufacturers.
OK, so here's a suggestion:
Messages are encrypted by a secret key K. That can be a per message key, session key, whatever. Apps use existing key exchange mechanisms, whatever they want, to establish K. Our goal is to ensure K is also available to the government.
To make K available, we could require that it be encrypted under a government public key PK, and the encrypted form shared with each message. The trouble is, who do you trust to control the corresponding government private key?
The traditional answer to this is secret sharing. Split K into K1, K2, ... Kn shares using an 'm of n' secret sharing scheme. Any m shares suffices to recover K, any m-1 tells you nothing at all (there are established mechanisms for this, e.g. https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing).
Now encrypt each share using different government public keys, PK1, PK2, ..., PKn. The corresponding private keys are held by different government agencies (police, courts, whatever). The bundle of encrypted shares is sent with each message.
Approved government decryptions require cooperation across agencies. Similarly, compromising the system requires collusion across different branches of the state. It's not perfect, but as I'm sure most Reg readers already know, the security of a real-world security system isn't about the crypto, it's about the human processes that manage the system. Sprinkle on some good key management and audit practices, and it's as good as you're ever likely to get.
And yes, I acknowledge there's significant message bloat to carry all the encrypted shares. These days, data is cheap and networks are fast.