Fix Google Play insufficient storage error without rooting my phone
This worked for me on my Sony Xperia E3 and my Galaxy Note 10.1: 
a) settings-apps-all-google play-uninstall updates (you will have to do this everytime you restart)
b) If this doesn't work: clear cache - with an app like 1tap cache cleaner or settings-storage-tap cache-clear cache.
:)