I know it's not possible to intercept any kind of event when an iOS app is uninstalled, but is there a way to bind keychain items to an app such that they will be removed along with the app?
No, there isn't. However, you can use NSUserDefaults to know if it's the first time your app is opened, and erase all keychain data, if it helps.