Your package name is unique. So if you want to change the keystore you will have to change the package name. If you change the package name Google Play won't know the apps are related, so nothing will be deleted. Google Play also won't accept your apk with the same package name if it isn't signed with the same keystore as the old upload.
To be clear: to use your existing PlayStore entry you need to use the same package name and the same keystore.
Afaik there is no possibility to automatically uninstall your app. You could try to wipe your data when starting the updated app. I would rather do that than force the user to download a new app, since not all of your users will do that.
See this or even better that for reference on how to delete your data.
What happens if you just update your app? Well, all of your code is replaced. It really is a reinstall of your app. However, only the code is deleted and reinstalled. Sharedpreferences (which are just some xml files android stores for you), downloaded and stored files etc. won't be deleted. Thats where you should delete the data. Delete the directories you created in order to save files. Nullify your SharedPreferences. But keep in mind that users won't like it if appdata is reset. Let them keep at least their logindata if possible.