Cannot activate iMessage/Facetime after change of phone number
According to Apple (https://support.apple.com/en-ca/HT201349) you should follow these steps:

"If the phone number that you want to remove belongs to an iPhone that you can't access, change your Apple ID password. This removes all phone numbers from your iPad, iPod touch, and Mac. Calls or messages for the removed numbers won't appear on those devices anymore.?

I would sign out of everything associated with your Apple ID on all of your devices before changing your password (including iTunes Store, App Store, iCloud, Facetime, iMessage, etc).  It saves quite the headache with password prompts popping up and things just not working properly due to things like 'Find My iPhone' being so stubborn. Having a backup of your iPhone probably wouldn't hurt either.

If this does not work I would strongly advise to call Apple. It's been a few years since I've had to troubleshoot this issue but if memory serves me well I believe there is something they actually have to do from their end if a phone number is 'stuck' to an Apple ID.