It seems plausible
I actually wanted to answer that such athing simply is possible, but to be sure one either has to find or design a protocol and I do not have time or skill to do either. I will however sketch what this could look like.
First of all elliptic curve cryptography is a kind of cryptography that is currently widely used in practice. As such it is a tested method. The idea is that people can exchange passwords with oneanother without an eavesdropper finding out what the exchanged password is.
Now there are infinitelly many different elliptic curves and for an elliptic curve protocol only one elliptic curve has to be chosen. This choice is important because some of the curves are essentially flawed and using them would be insecure.
It is however plausible that an elliptic curve can be constructed that is flawed in such a way that only the constructor can exploit the flaw. (e.g. The constructor might now the number of points on the curve or even the prime factorization of this number.) Exploiting this the constructor could be able to decript anything that was encrypted using this curve.
In your situation the government (or a department therof) should construct such a protocol and issue that to the phone companies. 484
As long as they keep the exact details of the exploit to themselves they will be able to eavesdrop on anyone.
Note1: This does mean that the government can be completely open about what they are doing. Since to actually use the backdoor you need the secret key that only the government has.
Note2: Great care should be given to keeping this secret key, really secret. This is however not impossible.
Note3: This is of course not perfect. Terrorist might simply decide communicate using a secret code of their own. But this is more or less the same as not using phones anymore.
Edit: I just re-read your post and noted that you did not want to let this rely on the government keeping things secret. This is still possible in a way. What can be done is embedding the final key in one unique object in a way that it can be used, but not recovered. So there is one physical device that can decrypt everything. 619