You will not be able to uninstall the GSearch app so easily. Even if you remove the app using any of the methods above, it will come back again. I would suggest following steps though it is not guaranteed -
1. Check if you have any other such app named GFirewall and Play Store. This Play store I am mentioning is NOT THE OFFICIAL STORE. If yes, try uninstalling them.
2. If you not able to uninstalling the apps, use any of your favourite Anti virus apps and quarantine all these three apps. That way, you may be able to solve the issue.