"This iPhone cannot be used because the required software is not installed. Run iTunes Installer to remove iTunes, then install 64-bit version of iTunes."
Let's try a standalone Apple Mobile Device Support install. It still might not install, but fingers crossed any error messages will give us a better idea of the underlying cause of why it's not installing under normal conditions.
Download and save a copy of the iTunesSetup.exe (or iTunes64setup.exe) installer file to your hard drive:
Download and install the free trial version of WinRAR:
Right-click the iTunesSetup.exe (or iTunes64setup.exe), and select "Extract to iTunesSetup" (or "Extract to iTunes64Setup"). WinRAR will expand the contents of the file into a folder called "iTunesSetup" (or "iTunes64Setup").
Go into the folder and doubleclick the AppleMobileDeviceSupport.msi (or AppleMobileDeviceSupport64.msi) to do a standalone AMDS install.
(If it offers you the choice to remove or repair, choose "Remove", and if the uninstall goes through successfully, see if you can reinstall by doubleclicking the AppleMobileDeviceSupport.msi again.)
Does it install (or uninstall and then reinstall) properly for you?
If instead you get an error message during the install (or uninstall), let us know what it says. (Precise text, please.)