I had to do an iPhone factory reset because before I changed the main email address of an Apple ID from a non-existing email address to a new email address, the user of the iPhone didn't sign out (by going to Settings -> iTunes & App Store -> tap on the field says 'Apple ID' -> click Sign Out). But before doing a factory reset, I need to backup the contacts.
Note: Restoring from iTunes backup will also restore the old Apple ID.
In this scenario, I'm using a Windows 7 computer with iTunes 12.1.1 installed and an iPhone 4S.
To summarise the restoration, I will be backing up the iPhone using iTunes, then extract the contacts from the backup using iBackupViewer. Import the contacts (VCF files) to Windows Contacts. Restore iPhone, setup as new iphone, disable automatic sync then sync contacts from Windows contacts. Then sign in on iTunes and iPhone using the new Apple ID.