If the keys and messages are known, yes, you can distinguish which were used - because you can test them all. If not, then this is "sligtly harder" (= not really possible with big enough values). Anything of the further answer will assume that the attacker doesn't know the keys or the messages.
The definition of HMAC looks like this: $HMAC(K, m) = H(K \oplus opad || H((K \oplus ipad) || m))$ with $k$ as the key and $m$ as the message. $opad$ and $ipad$ are constant, different values while $H()$ is the used hash function - in your case SHA-256. We can see that the end result is the output of a hash function. If there's nothing special happening with the key or the message inside the function, than all security features about the hash should also hold for HMAC. Finding the original message (while having the output of the hash function) should be hard - that's called preimage resistance. As long as the keys and messages were long enough, it shouldn't be possible (with non-ignorable probability) to find the orignal message in a reasonable time. Good hash functions should also be not distinguishable from truly random output, so this should also be no problem.
Even if you have every message HMAC-hashed with every key it is still not possible to say which HMACs were calculated with the same key / with the same message. The attacker will only see $1\,000\,000$ random looking bit strings ($1000$ keys times $1000$ messages) and have no clue what to do with them.
As soon as there are patterns in the keys or messages, it will be easier to attack the hashes. $80$ bit of entropy (from message and key together) should be enough to ward of any brute force attack. No hash is secure if the messages are small enough.
The document Keying hash functions for message authentication has more informations and the security proofs for HMAC. You can read there why it should be not really possible to find the used messages and key in your scheme - if they are big enough.