* A video call with a Facebook agent who verifies you.
* Uploading a picture of yourself holding a card that says 'Facebook', their city and the current date or similar. The city is something that FB can verify with IP address and account profile.
Yes, these aren't 'web scale' methods but I surely hope that they aren't just using OCR to validate Government IDs.