The problem is as follows:
There are two parties, both of whom would like to HMAC a message with a key. Although the keys are known to one another, both parties do not trust that the other one created a truly random key.
The HMAC result must not be easily attackable by a third party. So it is necessary the final key has substantial entropy whether or not one party didn't supply any.
In an optimistic world, both parties generate cryptographically secure 256-bit random numbers to key the message with.
In a less optimistic world, one party generates a secure 256-bit random number but the other party gives back 256 bits of data with hardly any entropy at all whether due to laziness or malice.
If both parties are lazy and/or malicious (worst case), then we can accept that failure is impossible to avoid. We assume for the problem that at least one party sees a good key as being in their best interest.
What would be the best way to structure an HMAC call so that I can use two keys such that one key being weak only means the strength is lower-bounded by the good key and not completely sabotaged due to some sort of subtlety?
The ideas I have are
HMAC(message, key1 || key2)
HMAC(HMAC(message, key1), key2)
HMAC(message, HMAC(key1, key2))
However, this is starting to feel like one of those problems where there is some subtle issue that I'm probably unaware of with all these seemingly straightforward choices.
After some discussion below, I feel I may need to include some more important details.
Party 1 will hand off an allegedly random 256 bit string to Party 2. Party 2 will also generate an allegedly random 256 bit string. Party 2 will be responsible for generating the HMAC but Party 1 will have the opportunity to reject the result. Both parties know each other's secrets and at least one party cares about having a strong secret although it is possible that the other party is malicious or lazy.