What kind of privacy expectations could a person using a phone that would allow this have? In fact this is the kind of thing that has caused trouble for Google and Apple both. Especially given your requirement to have the "contact", a lot of users might be very wary of this if you tell them. If you don't, well then its pretty close to spyware.
That being said, you could intercept phone calls, sms messages and probably emails rather easily with broadcast receivers. All those other things would take more effort I think. If they accept a push model like the phone and sms then they might use the same broadcast receiver solution but some of them might have to be initiated by the user.
Here's my favorite tutorial for sms to get you started:http://pankajchunchun.wordpress.com/201 ... n-android/
Hope this helps.