How does a miner know which nonce to start with ? Pretty straightforward question : 

When a miner is trying to find a 18-leading-zeros hash, does it always start with a nonce at zero ? I suppose it doesn't, because other miners in the world may have found out that the first 1000 nonces won't give a sufficient hash. 

My question is then, how does a miner knows which nonce to start with ?
The entire block header enters as input in the hashing process.

Along with nonce and some other fixed fields there is a "Merkle root" field in the block header that each miner has different. 

So each miner can search the nonce range from 0 to the last - in order; because of different Merkle root each miner will have different block header hash for the same nonce and other fixed fields.

NOTE: Why each miner has different Merkle root? That's because in the transactions miners include in the block (from which Merkle root is derived) there is one special transaction called "coinbase transaction" that each miner has unique. Therefore the Merkle root is also unique. "Coinbase transaction" is included by the miner himself along with regular transactions and is the transaction that gives mining reward to miner's own address.