Solutions so far seem to boil down to either "trust other people" (multisignature wallets) or "trust your devices" (a la Keybase: https://keybase.io/blog/keybase-new-key-model ).