Any particular guess-and-hash operation has a certain probability of finding a solution, and that probability is the same for all systems, no matter how fast or slow they are running. Faster systems just guess-and-hash faster, and thus have more opportunities to succeed. That difficulty is set dynamically based on the estimated total rate of operations, or hashrate, of the entire network, so you can think of the system overall doing a certain number of hashes per second. A solution is essentially a random event that one particular hash will satisfy. So the higher the hashrate, the higher the probability that you will succeed, but it's still a probability. You never have a guarantee that you will succeed, no matter how fast you are, and even slower systems have a chance.
That's why there are these malware-created networks of low-power systems doing bitcoin mining. They're all pretty slow, but with enough of them working, one of them will succeed every once in a while.
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.
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.
Does that make sense?