So, to get a handle on what you are looking for:
A simple private public key pair is no good because while one user belongs to each pair, many pairs can belong to one user. You want to make sure no one can have multiple identities?
Here's the bar to beat cost wise. Hold everyone down at gunpoint, implant a heart monitor that explodes when removed and communicates with your server continuously.
Correct, a simple private key pair is not sufficient.
I realize that the second example is a joke, but willingness is a necessity, not a preference. Only people who volunteer and want to be verified will be verified, but there will be some people who want to be verified more than once. Also, your solution is by no means cheap.
One idea is to do periodic DNA tests which can be used as the private part of a cryptographic pair. The DNA labs would have to be independent and be audited by independent auditors who also audit one another. This pretty well solves the problem, but much too expensively and too difficultly. The challenge is now for someone to come up with a better solution according to the metrics of high practicality, low difficulty and low cost.