Selective removal of permissions
If you're not afraid of rooting your phone, there are two excellent third-party solutions to this problem.
The first one is to install CyanogenMod. Then when you go to Settings --> Apps --> Manage Apps (or wherever you can view an app's details), at the bottom of the screen where the app's permissions are listed, tapping on any permission will toggle it. This is what Google should have added to Android in the first place.
Downside: this requires a factory reset.
A more elegant solution is LBE Privacy Guard, a simple app that requires root privileges but can otherwise be installed just like any other app on top of your existing system. Its permission management is not that fine-grained, but it has one huge advantage over CM - instead of actually giving the app a slap on the wrist when it attempts to use a permission that has been revoked, it'll intercept the API call and feed it false information.
I've used both solutions (separately) for some time and prefer LBE Privacy Guard because it's more elegant: ...
An app that wants to use a revoked privilege on CM will get an "access denied" message. Some apps aren't designed to cope with this and will crash.
An app guarded by LBE PG on the other hand will simply see an empty phone book, an empty message list, a phone serial number consisting of all zeroes, etc. depending on the permissions you've revoked. It's tricked into believing it still has the revoked privilege but there's simply no data worth looting.
In addition to granting and revoking permissions, LBE PG can also be set to ask or alert you each time an app wants to use a certain privilege.
Paris, because she's been rooted countless times.