I'm afraid that only Facebook and Microsoft can solve this.

However, if you read David's story here: http://www.zdnet.com/article/locked-out-of-instagram-in-social-space-no-one-can-hear-you-scream and realise that your value for Facebook and Microsoft is a few dollar a year, you can only hope for the best.

Making a new Facebook account (and not forgetting the password of the mail account you for that) seems the most likely way to handle this issue.
Ever thought of using a password manager to safely store all your passwords? I can really recommend it.