The simplest way to export all your Facebook Contacts, as I tested it in person, will takes you only 2 minutes.
However, it took me some 2 hours to find out this method, after trying bunches of outdated methods and broken apps.
And “Hello Mark, you know you’re not a bad guy, but you’re trying so hard to be.”
Thanks Google and Yahoo, Data Liberation for the win!

Steps:

  1. Create a Yahoo! email account
    (Better use an existing one, or you have to wait 14 days. Just Rule.)
  2. Goto “Contacts” tab, Import your Facebook contacts into Yahoo!
    A Shortcut named Facebook will be automatically created.
  3. Click Shortcut Facebook and Select All then click Assign to Lists.
    (see image below)
  4. Finally, Export All contacts in the List you created.

Note:

Again, you’d better use an existing Yahoo email account, or you have to wait 14 days. (I hate rules.)
You can’t directly export contact in the Facebook Shortcut created by Facebook. (Mark won’t be happy.)

 

export Facebook Contacts