In the settings your app on facebook, click the "advanced" tab
In there is a setting for
"Deauthorize Callback URL:"
This url is pinged when a user deauths your app. I'm not sure how "realtime" it is, but I assume it's pretty quick
I'm not 100% sure on the parameters passed to this, so you might have to create a page that logs the $_REQUEST somewhere so you can inspect, but I know the users UID is in there somewhere. Then you can perform whatever clean-up you need to