How I got this error
it is strange. My app was working perfectly until I change some list definition in my source. suddenly I got this error. I tried to revert the definition and deploy it again but still it gave the error.
You can try following steps
Retract the app using visual studio, and check the site collection whether it is available in Site Contents. if so first remove it.
Then check the app availability in Apps Packages and Apps on testing lists. if it is there delete it.
Then check the recycle bin and Admin recycle bin and empty if any.
and tried to deployed the app.
If it is not working you may have App deployed to other sub sites as well. So go there and delete every thing.
If it is a O365 , go to Share Point administration
then Go to Apps –> App permissions and delete the items related to the app.
if this wont work , try with new site collection.