Some Android projects showing how to do stuff without having the permissions. Compiled versions and background information can be found at http://www.macmark.de/android.php
Internet: HelloDroid has internet access without permissions.
Remote Shell: CmdDroid reads commands from a web server without permissions and executes them.
Contacts: ContactSucker reads contact data without permissions with an inter app service from TroyDroid.
Phone calls: CallDroid does phone calls without permissions with an inter app service from CallBoy.