An elegant solution here might be to allow users to designate a list of other users who can "vouch" for them; if multiple people who you previously designated as trustworthy say "hey, this is my friend's new phone number, use it instead of the old one for account recovery", then that should satisfy the "who you are" authentication factor (and set the new "what you have" factor).

Similar idea behind web-of-trust or multisig cryptocurrency wallets, except without the cryptographic mumbo-jumbo.