I just stumbled upon Solidus, a proposed Cryptocurrency based on permissionless Byzantine Consensus:
In summary, this work presents Solidus, a scalable and incentive compatible cryptocurrency based on a fault-tolerant committee and permissionless Byzantine consensus. It is secure against withholding attacks such as selfish mining and provides instantaneous confirmation of transactions. Perhaps a limitation of Solidus is that the protocol is currently rather complex. It remains interesting future work to simplify and improve the Solidus protocol.
Solidus uses PoW for leader election to adapt the Practical Byzantine Fault Tolerance (PBFT) protocol to a permissionless setting. It comes with a whole set of incentive
mechanisms for different kinds of actions. As far as I can tell, it's far more sophisticated than BitcoinNG and ByzCoin and (promises) offers quite some advantages over them. However, it still relies on the assumption that at least 2/3 of the computing power is controlled by honest nodes.