When the app is initially installed subscribe to appuninstalled webhook. When the app is uninstalled Shopify will send you a request signifying the uninstall action. Prior to this you can assume the app is installed. Without an access token you can't send valid requests to Shopify API so your choices are limited.
In that case write some application logic that updates a timestamp on your database when the customer logs in so you know they are active. Or you can subscribe to the appuninstall webhook the next time they use your app like after authentication and then all your existing installations will be fine. The ones in the past that never subscribed I think will be somewhat a hack to do this. Or you can simply email your merchants and ask if they're still using it, just a thought.