maaku's explanation makes clear a very good point - trying any particular hash only tells you whether that one succeeds or fails; it doesn't tell you anything about whether any other value will succeed or fail. Any particular hashing device will maximize its chances of winning/finding a solution by trying nonces in such a way that it is unlikely that any other device is trying the same ones, but that it never tries the same one itself twice.
I don't know offhand how many mining algorithms are out there and how they go about picking nonces, but I'd bet they do something like pick a strongly random starting value and then increment it by a fixed, small amount each try.
But yes, all of the miner's blocks are generally different. Each block that a miner is working on must have special Coinbase transaction that awards a specific number of new BTC to a chosen address. If you are an independent miner, that would be your address, but pool miners generally use a pool address. I don't actually know how the latest pool mining algorithms work, but I think they all have more elaborate systems for how payouts work.
The block includes a nonce, a random number which is changed for each try until one gives a hash < target. That nonce is picked at random independently by the miners, so that also makes the blocks they are working on different.