Is it possible to combine two hash functions in such a way that cracking the constructed hash would require cracking the constituent hashes? Suppose A is some arbitrary hash function, for example BCrypt or MD5. And B be some other arbitrary hash function, maybe SHA256 or SCrypt.
Let passwordHashedWithA = A(password) and  passwordHashedWithB = B(password).
If an attacker is given just passwordHashedWithA and finds a pA such that:
passwordHashedWithA == A(pA)
Then the attacker has performed a successful preimage attack on A.
I want to know if it is theoretically possible to construct a hash function C out of two arbitrary hash functions A and B, such that for any A and B, performing a successful preimage attack on C would require performing a preimage attack on both A and B. The question can be extended to build C from N arbitrary hash functions.
I strongly suspect that this is theoretically impossible; it seems like a free lunch. But I cannot begin to think how to prove it.
If such a thing does exist then it would be incredibly useful: we could combine old, proven hashes like BCrypt with slightly newer and fancier hashes like SCrypt, such that we have the best of both worlds. Like I said - sounds too much like a free lunch.
I am asking this from a theoretical perspective, I'm aware that BCrypt or SCrypt are probably good enough for most production systems.
I'm looking for a proof that this is impossible, or a construction of C that provides these properties.
Examples of C that don't work
Suppose we try C(password) = A(password) + B(password) where + is just concatenation of the hashes.
The result of this is obviously a weaker hash: we can preimage C by finding the original password by cracking  A or B.
If we try C(password) = A(B(password)), this initially looks stronger but you really can't say much about C without looking at the specifics of A and B. For example if A was a completely useless hash that always returned a constant string, the strengths in B would be irrelevant, and any string would be a preimage of C.
Suppose we try C(password) = A(password) + B(password) where + is just concatenation of the hashes.
The result of this is obviously a weaker hash: we can preimage C by finding the original password by cracking  A or B.

This is incorrect with the standard notion of preimage resistance.
Because there are many more possible inputs to a hash function than outputs, there are necessarily collisions. Even if $A$ allows you to find a preimage, that is not necessarily a preimage for $B$. For random inputs and unrelated hashes, it very likely is not.
In practical applications this is quite a bit more messy. For example, if you take $A$ to be the truncate function (to e.g. 256 bits, zero-padded), it lets you find a preimage for the concatenated hash if the input is short enough. For the vast majority of possible inputs it does not directly give you a preimage, but that is cold comfort if hashing e.g. typical passwords.

If you want a provably robust combiner, you could look into the thesis linked from an answer to the previous question: Anja Lehmann: &quot;On the security of hash function combiners&quot; (pdf). It offers good combiners that are unfortunately rather complex.
For a simpler combiner, you could use XOR like TLS does. You do not get a nice proof from only the preimage resistance of the hash, but it is provably PRF if either of the two password hashes is PRF (and they are independent). That is a practical choice that is probably good enough if you take care to use different hashes.