Further thoughts:

Anyone would be able to add proofs of work onto this kind of chain, continually making it stronger, by submitting zero-value transactions.  Peers who recently submitted transactions would be motivated to do this to ensure their transactions get sufficiently buried.  They could even pay others to do this for them if they wanted, which would be just like transaction fees in the current system.

You could still have coin-generating transaction blocks with a set target difficulty -- they would just include the one coin-generating transaction, though, but would need to have a reasonably current set of predecessors to be accepted.