Allow me to introduce myself, I've finally found a solution to this problem.
After all my hard-work and research, I bought a new Samsung Galaxy S6 active and I haven't been able to set-up my google play store account because I kept getting "unfortunately google play service has stopped working" message.
If you follow these steps I will guarantee you, you WILL have your google account and play store up and RUNNING AGAIN. But you have to bare with this process and trust me.. I was trying to fix this issue for the past 2 days.
To start with, this problem has nothing to do with clearing the cache so STOP clearing the data and the cache, nor force stopping, nor putting your phone into SAFE MODE. The REAL problem here is the Google Play services app version is OUTDATED. Either the phone was purchased with it outdated or it just hasn't been updated automatically.... unfortunately if you do not have Google Play Services working you cannot update it through the Google Play store (which is where it originally updates from) because the play store is also outdated... so in other words Google Play services is the backbone of all other Google Apps such as Google Play store, Google Plus, Google Books, Etc..
HERE IS THE FIX in 10 steps:
1. You need to connect your phone via USB to a computer.
2. Make sure your device is able to transfer media files (or Files in general) using a File Manager that the phone normally has installed already to be able to transfer files from computer to phone and vice versa.
3. Go to settings > Lock screen and security (or something similar) > Unknown Sources (slide to ON position) (Click OK and agree to Allow installation of apps from sources other than the Play store). This allows you to transfer a file you will need to download later from your computer to move into your phone.
4. Go to settings > About Phone (or about device) > Android version (write your android version down) For example: 5.0.2 or 6.0.1, etc..
5. Go to settings > Applications > All > Google Play Services > (write your version down, INCLUDING the number series in the parenthesis)
6. There will be 3 numbers together in that series separated from a dash inside the number series in the parenthesis.. these are the key 3 numbers in the next step. For example (228-xxxxxxxxx) or (440-xxxxxxxxx) and it can be in the opposite form of (xxxxxxxxx-448). You need those 3 numbers write it down.
7. Go to this website
Google Play services 9.4.52 APK Download by Google Inc. - APKMirror
8. With those 3 numbers you will be able to identify which correctly updated Google Play Services version fits your phone. It is like a puzzle. Follow the steps on the page to find the correct APK file. (Follow the XYZ method on the page and match the corresponding X with your android version and so on and so forth...) Make sure you find the correct Google Play services version for your phone or else it will not work.
9. Once you find the correct version, click on it, it will take you to the page where you can download the APK File. Click on "Download APK" Download it to your computer first and make sure you know where it is being downloaded to, THEN using your computer move the file to a file in your phone. Open your phones storage and look for a file, for example, "Download" is a file on the phone you can transfer it to which is what I used.
10. Go to your phone and look for that file. Click on it, it should be an APK file. When you click on it, it will open just like a .exe file would on a computer. Install it on the phone for the first time and you will be done.. You have now replaced the old Google Play Services APK file with the correct one and you should be able to access your Google Apps and Play store account WITHOUT any error messages when you set-up your Google play store account for the first time on a new phone or even on an old phone with this error message.
Hope this helps, It helped me. Any questions.. just ask. Thank you.