Why change the nonce instead of just rehashing? Why do miners increase the nonce to compute a block hash rather than just generating a random block hash?  It seems to me that both approaches would have the same likeliness of finding a result that is below the target.  

If the answer is that it is quicker to increase the nonce instead of just generating a random hash to find a valid result, could you show this in a mathematical/statistical way?
The hashing function used in Bitcoin is deterministic, that is hashing the same input, i.e., block header, will always result in the same output. This is necessary so that others can also check that a Proof-of-Work is valid.

This means that in order to compute a new hash the input to the hash function needs to be altered. The easiest way to alter the input is changing the nonce since this is a free-form field that may take any value. Other ways to modify the input is for example swapping transactions or modifying the coinbase transaction, which would require that the merkle root be recomputed in the header. The timestamp is also a popular choice, however its values are limited by a range of acceptable times.

In case you are wondering why we don't simply rehash the output of the previous hashing function to get the next value: this would destroy the proof-of-work mechanism, which requires an easy to verify proof that the issuer has performed some work. The key here is easy: if we iteratively hash the results of the previous solution then the verifying party would also have to perform this work to check that the issuer has performed the work. when varying the input this does not happen since given the input the verifier can perform a single hash operation and check the result.