Ripple is an example that works without proof of work nor proof of stake (so no nonce needed). This does open it upmechanism is more vulnerable to sybil attacks, so it needs strong peer identity knowledge (but not trust!) to be secure. See https://ripple.com/wiki/Consensus.
