Web of trust is the right solution, if you do it right. It models the situation with paper credentialing rather nicely, and society seems to function pretty well on that system.
The key is that each side needs to be able to easily specify an automatically-checkable trust policy that meets its needs. There is no one "right criterion" for deciding whether to trust a counterpart---different situations and different counterparties demand different levels of trust verification. If the web of trust is treated as a credentialing mechanism, and a trust policy is used to check for the right credentials, then this to my mind is a far better solution than any centrally-run identity-based one.