Even when using the getExternalCacheDir(), I have seen that the cache directory, which is your app's package name, is not removed automatically as it says on the Android Documentation, at least not on the Lenovo A1. It could be a bit naive but you may want to clean up previous data during re-install. There, you can find out if your app was un-installed or is being installed for the first time - you store a value, perhaps a boolean, using shared preferences. It can be something like:
SharedPreferences sharedPrefs = getSharedPreferences(INSTALL_PREFS, MODE_PRIVATE);
if(sharedPrefs.getBoolean("AppInstalled", false) == false){
//DELETE APP DIRECTORY
SharedPreferences.Editor editor = sharedPrefs.edit();
editor.putBoolean("AppInstalled", true);
editor.commit();
}
This way, everytime the app runs, it checks if it's the first time it's running. When the app is removed, so will the shared preferences for the app. Then, the next time it is installed, the if(...) will be true and you can do some clean up there.
I know this doesn't answer the question directly and it's not nice to leave unused data on users' devices, but I think it could be an alternative to trying to clean up when an app is being removed, which is sensible but seems impossible.