I had the same problem recently. The phone was constantly reporting Google Play Services and many others as having stopped. A hard-reset left me unable to complete the initial setup, as the account manager kept stopping too. My S3 was stock standard, not rooted or running any custom firmware. I was able to fix the problem, and I'd like to share my solution.
Download Samsung's "Kies" software. Searching the samsung.com site pointed me to Version 2, but once installed the software self-updated to Version 3.1. A restart was required after installing (I'm on Mac, but I understand with will work on Windows too).
Power on the phone. Start Samsung Kies software. Without touching the screen, I connected the USB cable to my computer.
Tools > Firmware upgrade and initialisation
I was warned that the current firmware was already installed, but chose to proceed anyway. The current firmware was downloaded and installed on the phone, which took around 20 minutes.
After restarting the phone, I was able to complete the setup process without any errors. The OS now appears to be working correctly (Android KitKat 4.4.4). If I had to guess, I'd suggest it was some older versions of my network's own customisation that was incompatible with recent Play Store Services updates. Interestingly, my phone now has less added software (only 2 extra apps I can see) and seems to run better than it did originally.
I hope this info helps others too.