What prevents a miner from faking nonce hash What exactly prevents a miner from presenting a random nonce hash of the block with enough zeroes at the start to get chosen?

How is the new hash verified by the other nodes? Since as I understand there is no 1 valid hash outcome, but multiple? What are the conditions other than having a number of zeroes at the start?

Instead of incrementing the nonce, could you intelligently pick a random higher nonce and see the amount of leading zeroes increase? Or is there never any direct relation between the nonce value and the resulting hash? (Probably, but I need to have this confirmed)

Mainly, what prevents a miner from having a pre-calculated database of sufficiently difficult but random nonces/hashes that could be presented instantly and could be accepted? 

If the new hash only has to be equal or lower than the target? How do you verify that work has been done, without doing the same work yourself?
No correlation between any input bit or combination of bits and any output bit or combination is acceptable for any cryptographic hash. SHA256 is an accepted cryptographic hash.

Anyone can (and many do) verify a valid block by doing one hash operation, rather than the huge number it takes to find by brute-force, currently on the order of 1,000,000,000,000,000,000,000.

EDIT: I somehow computed 4 bits per byte not 8 (BIG difference), plus forgot the prevhash prefix. Corrected and also clarified some.

In addition to nonce, miners can tweak a few bits in time and use maybe 20-40 bits worth of choice in the Merkle root (by changing extranonce and/or transactions) in the time available. Plus part of prevhash is always the same (namely zeros) -- at least as long as the database 'shortcut' doesn't work, and it doesn't. Let's call it 80 160 bits total, meaning a complete database would be about 2^{240} 2^{480} entries. But we can't store that much, especially not since it must be accessed in significantly less than the normal mining time of 10 minutes. And since we can't know in advance which entries will be needed, no matter what subset of the database we store it's a "roll of the dice" for each block header whether it is in the database and thus "pre-mined".

If you use all of the roughly 2^{190} atoms in the Solar System (and move them close enough) and can store one header per atom which is many thousands of times denser than any known storage technology, your database will 'hit' (contain the desired solution) with probability one in 2^{290} which (since trials are independent) will occur for (rounding slightly) about one block every 20,000,000,000 20,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 years, which is probably almost certainly longer than the universe will exist. (And certainly not often enough for you to make any profit from it.)

See also https://crypto.stackexchange.com/questions/1013/is-it-feasible-to-build-an-index-of-prime-factors for several discussions why a similar approach for breaking RSA is ludicrously infeasible even without the short time limit needed for Bitcoin.