I didn't mean trusted timestamps, though I don't know what kinds of them exist.
The one with the most hash iterations has gotten it first. By "fair" I meant the same serial iteration h(h(h)))... speed, so parallelism doesn't help like it does with searching preimages, it's bound like the time lock puzzles. E.g. both provers having a hasher that can do X single core instructions a second, one can prove to be ahead because he started earlier, and for the verifying he sends a keyed hash, so when the behind-clients have iterated to the same count, they see who was right / first and nobody could have catched up. You could prove being ahead in iterations forever and the hash tree would just be there so that you don't need many hashers, you only take in a new hash leaf, which itself proves its iteration count and the top hash iteration count is then added. So one could prove it for as many coins as they like.
(?)
Ok, you're talking about replacing the incremented nonce hash with hash(hash(constant))....? That would completely remove the random component from hash solutions, meaning the guy with most CPU power always wins the race, which leads to massive centralisation problems.