This is definitely a weird issue and I’m not quite sure I totally understand, but I’ve got a couple of suggestions for you.
In order of easiest to most difficult,
- Try to manually set the time, date, and time zone. (Settings|General|Date & Time, then turn off “Set Automatcally)
At one point you state “The time and date are completely incorrect”. I don’t know for sure how the apple services are set up, but normally for things that need to sync like that a little leeway is allowed as there can be short delays as data travels over the network. If the time and date are way off then it definitely won’t work, but If you can manually set the time and date, ideally to within a few seconds of the correct time, then it may work.
- Try to reset all settings (Settings|General|Reset|Reset All Settings)
Despite the name, this will reset most of your settings back to the factory defaults (Some things, such as having Find My turned on will remain). But if the issue is some weird corrupt setting that’s preventing it from automatically updating the time then this might fix the issue and allow it to set the time automatically.
- Finally, if both of the above fail, put the phone in DFU mode and connect it to iTunes to reinstall iOS
This is similar to what you did above when you put the phone into recovery mode, but DFU mode will allow it to be restored without doing any checks on the phone or turning off Find My. This means that the phone will still be activation locked, so before you sell it you’ll want to go through the activation process where it will ask for your AppleID and password to turn off activation lock.
Good luck