They could use multiple signing keys. One in America, one in Hong Kong, one in Germany, etc. If a firmware update is not signed in all (or N of M) jurisdictions, the secure enclave simply rejects it.
This is an excellent solution. A bit like Ripple's concept of trusting a set of validators are unlikely to collude against you, without having to trust any single one of them: https://wiki.ripple.com/Consensus#Not_colluding
Of course it doesn't stop any particular government from making it illegal to sell unbackdoorable phones in their country.
This sounds like a good case for a threshold signature scheme[1] where no one member has all of a complete key and can partially sign without revealing their piece of the key to anyone.
Aren't all algorithms "clever" at some level? I assume you are implying non-mainstream - that always carries risks, but there are some advantages:
1. The software that verifies the certificate doesn't need to be changed - which is quite an advantage if it has already been shipped, or if you need to change the signing rules at a later date.
2. The verification logic is exactly the same as if checking a regular, single signature certificate. Nice and simple, no bugs related to whether all criteria have been met by multiple certificates.
Here's another possibility. Let's say DOJ wins, or a new law is passed requiring Apple to sign malware version of iOS. Apple risks losing huge market share overseas, where people will stop buying iPhones. Apple spins off affiliate companies in these other countries, distributing controlling share of the affiliate stock to current Apple shareholders. Then apple just licenses its tech to the spin-off affiliates. No control over their ops. (Obviously would be more convoluted, much more -- but that's the basic idea.)
Of course it doesn't stop any particular government from making it illegal to sell unbackdoorable phones in their country.