The "blocks are never final" idea is what I believe has led to some of the proposed 51% attacks on the bitcoin network.
Question: Does proof of work have to be a near 'lottery' system? Obviously it needs to be asymmetric, but are there other good options than hash collision?
As for "lottery", I believe the answer is yes and no. The basic point is to raise the cost of "faking" a confirmation, and how you do that is completely up to you - e.g. captchas are a great example! That said, the random part of the non-deterministic process provides a lot of really nice properties for a distributed system - fairness claims, etc. That said, this is a deep topic (with lots of caveats) in its own right.
There are indeed other proof-of-work algorithms. Probably the first one is Primecoin, which asks for a Cunningham chain of prime-numbers.
My own Cuckoo Cycle, asking for a cycle in a huge graph, is another example, in which a single proof attempt takes hundreds of MB of memory, but verification is instant and takes no memory.