I think that a lot of the confusion comes from thinking that there is just the one true next block and everyone is trying to find the one.

That isn't how it works.  There are many blocks that could be the next one.  The difficult part is finding one out of the much huger number of blocks that aren't difficult enough.

Each node builds up a list of pending transactions, and they pick some or all of them to go into the new block.  Once they have their list of accepted transaction, they calculate the hash of a Merkle tree for that list.  One of these transactions is unique to that node too, because it is the generation transaction, and everyone gets to pick their own account for the reward.  So, even if everyone had the same rules for picking and ordering transactions, they would all be starting from different places anyway.

For many potential blocks, there is no value of the nonce that will give a hash less than the target.  When that happens, the node must alter something in the block header and try again.  The timestamp is a good candidate, since it usually takes some time to try all 2^32 nonces.  New transactions may have come in across the network that can be added to the tree too.

I could have sworn there was also a nonce in the Merkle tree calculations, but I can't find any references to it now.  Ahh, theymos found it while I was typing.  It is in the generation transaction, which changes the Merkle hash.

In a pool, the pool server will hand out unique headers to each worker/request, by using the extraNonce and rehashing the tree, to prevent duplication of work and get better odds of finding a valid block.