There is no guarantee to find a hash by exhausting the entire 32-bit nonce space even at difficulty = 1. Which is why miners have always used "extranonse" which can be found in the signature script of the coinbase transaction and most early blocks have a non-zero one which indicates multiple nonces were checked from 0 to 2³² before the result was found.
Another alternative to extranonce is updating the block time or rearranging the transactions in the block but this last one doesn't apply to early blocks.