Android google play no connection error
I feel your pain, this has happened to me. It's very frustrating. I tried clearing cache for apps, removing them using the application manager and a bunch of other unsuccessful attempts. The only thing that helped was a factory reset. Luckily I was able to backup my data prior to doing a full factory reset. I know you mentioned that it's something that you don't want to do. The only other option would be to root your device and flash your device with a new ROM - but doing this would essentially be a pseudo reset, so if this seems like a valid option, I would play it safe, backup and reset.  

Also, you mentioned that you were able to read the host file? Do you see any specific URL's or IP addresses in the "hosts" file? If so, you want to clear anything that says Google play. Leave only the first two lines - which should be something like:

127.0.0.1    localhost
x.x.x.x:port*


Where x is variable and :port would be defined

I found a thread on XDA forums that might help - but it requires Root. 

Tested FIX for Google Play Connection Error

Let me know if this helps.