Take this lightly until confirmed, but here's my understanding...
There is no variation in the problem itself - every node is intended to work on the same block at the same time (accounting for latencies and such). The luck factor is really the random number generated at the beginning of each node's attempt to solve a new block. When a new block needs to be solved, each node generates a random value (nonce), which is used to hash the block. If that hash isn't the right one, the nonce is incremented, and the new incremented value is used to hash the block again.
You are right about the nonce and the hashing, but..
Everybody is working on a different block.
To pay the block creator 50BTC you need to know the Bitcoin Address it needs to go to.
For the block creator to be able to spend the 50BTC they create, they need to have the private key associated with the bitcoin address the 50 was paid to.
Since everybody has a different private key (randomly generated), everyone has a different Bitcoin Address (associated public key (hashed))
Part of what makes up the block is the hash of the transaction that pays the 50BTC to the block creators Bitcoin Address.
This means that everybody has a different block.
Whoever solves their block first 'wins' and that block is acclaimed by all as the 'next' block.