I actually didn't go far enough with these steps.
You also have to assume your ex may have installed a keylogger or other malware on your Mac. It will be a complete waste of time to do all of the above if the first time you type in the new ID and password from the Mac, it gets passed onto him.
So, to add to the misery of a severe cleaning. Go through the steps of backing up your phone's personal data. The images and videos now MUST be copied to another drive since you're also going to be wiping your Mac.
On the Mac (assuming you have all of the same contacts there as on your phone), open Contacts. Select all names. Right click anywhere in the list and choose Export vCard. Save the file to the desktop. Make sure to copy that file somewhere off the computer's main drive so you can get back at it later. The same place as your stored iPhone images is good.
Make all other necessary manual backups from the Mac. Your emails, word processing documents, etc. Time Machine is useless here. You can't restore that for the same reason you can't restore your iPhone's backup. You'll just put any possible malware back.
Once you're certain all personal data has been backed up, restart the Mac and hold down the Command+R keys. When the work screen appears, go to the top menu and run Disk Utility. Choose your Mac's main drive at the left and choose to erase it.
With the drive now wiped, close Disk Utility. From the work screen, reinstall the OS. Once done, you'll eventually end up back at the Mac's desktop as if it's a new Mac.
The tedium continues as you restore all of your personal data manually from the backups you made. Again, DO NOT merge in a Time Machine backup. Reinstall all third party software only from the original disks, or purchased downloads.
Now create your new email address, followed by your new Apple ID and password linked to that new email account. If there was a keylogger or other method your ex could have possibly been using to watch your actions, they're gone now.
No, this is not fun. But wiping everything is the only way to ensure you've removed all possible means of seeing or capturing what you're doing.
When you restore the Contacts list on your Mac by importing the vCards you saved, there's a really easy way to get them back on your iPhone. Email the saved contacts file to yourself. Double tap the file on the iPhone. It will ask if you want to import all contacts. Say yes. Done.