My solution to this is to embed key signing in everyday face-to-face activities. If your wallet gets signed every time you buy something, soon it will have useful identity. https://www.wired.com/2014/07/document-coin/