The merkle root changes everytime the transaction selection changes (or transaction order). The timestamp changes. The coinbase transaction changes the address(es) that is pays out to.
All the miners in the entire network aren't all working on the exact same block.
As gmax alluded to, this is all irrelevant. The nonce itself is part of the block. If the block's hash does not fall under the target difficulty, a new hash (read: block) is created by changing the nonce. I think the OPs question is more "given a set of transactions and a single timestamp, is it possible that all 64-bit nonce values could be exhausted without finding a hash that beats the difficulty?" and the answer has to be yes, or the hashing algorithm is suspect. But the odds of this are definitely related to the difficulty, somebody better with math than me would have to work that out.