OP_DUP OP_HASH160 key1 OP_EQUALVERIFY OP_CHECKSIG OP_VERIFY OP_DUP OP_HASH160 key2 OP_EQUALVERIFY OP_CHECKSIG
That will work. The keys in your example would actually be key hashes. You can use OP_CHECKSIGVERIFY for the first OP_CHECKSIG to make it a byte smaller.
The scriptSig would look like:
<sig2> <key2> <sig1> <key1>
If you can use full public keys in the scriptPubKey instead of hashes, it becomes even more compact:
scriptSig: <sig2> <sig1>
scriptPubKey: 2 <key1> <key2> 2 OP_CHECKMULTISIG
With OP_CHECKMULTISIG, you can also change the first 2 in the scriptPubKey to a 1 in order to require
either key1 or key2 to sign. And you can specify up to 20 public keys with a single OP_CHECKMULTISIG.
Your "keyA AND (keyB OR keyC)" is as simple as this (assuming you can use the full public keys):
1 <keyB> <keyC> 2 OP_CHECKMULTISIGVERIFY <keyA> OP_CHECKSIG
Even when using key hashes, you can use stack ops to manipulate the stack into a format that can work with OP_CHECKMULTISIG, but I don't think that's better in this case. Too bad Script has no loops.
This is all filtered by IsStandard in the current version, but you can probably get new versions to accept it if you create something that uses it.