Is it possible to detect Android app uninstall?

Unfortunately the ACTION_PACKAGE_REMOVED intent will be sent out to all receivers except for your own. This is confirmed here.

Some questions for your C2DM plan, since I'm not very familiar with it. If the user just leaves their device off for a long period of time, will that trigger the error condition you use? How does C2DM actually report an "unreachable" device? Is that a condition that only occurs when it attempts to send the push notification and fails or is it when it somehow determines it reaches the device but fails to be handled properly? Obviously in the second scenario your plan would work, but I can see some "false positives" occurring otherwise.

Older SO question for reference: android not receiving Intent ACTION_PACKAGE_REMOVED in the removed package

The GCM documentation explains this situation here:

https://developers.google.com/cloud-messaging/registration#how-uninstalled-client-app-unregistration-works

"An application can be automatically unregistered after it is uninstalled from the device. However, this process does not happens right away, as Android does not provide an uninstall callback."

Basically when GCM tries to send the next push notification, the device will tell GCM the receiving application was uninstalled.

As for notifying friends that their friends aren't using the app any more, GCM will send a NotRegistered error to your notification server when this failure occurs; it won't be immediate, but could you use that?