It isn't just the nonce that increments to find a valid hash, you constantly hash the block header completely. The block header contains other data such as version, hash of previous block header, merkle root, time and bits. Your merkle root hash will be different to everyone else. This means no-one else is hashing the same data.