@JJS
"or using data will prove just as ineffective as UAC on Windows."
Except it is effective on Windows. Vista took a lot of heat for UAC but there is no denying that it forced applications to become good citizens by not requesting permissions (e.g. read/write access to parts of the registry) unless they strictly needed them. It served its purpose which is why prompts are relatively rare these days.
Secondly a UAC like mechanism forces user intervention. If an app decides to send SMS messages then you will get a prompt up. If you didn't initiate this SMS sending, it should serve as a massive clue to the user that something is up. At the moment the app could send 10 messages to a £3 premium service overnight while someone was asleep and they would be none the wiser.
Thirdly, I have already said how people could disable the prompts. Each app could be governed by a security policy - trusted, untrusted etc. If they get fed up of the prompts or wish to trust the app, the UI could make it simple to flip the security policy.
The point being that a secure by default policy, plus the prompts when apps do naughty things will serve to make apps better citizens and provide a measure of defence which is sorely lacking at present.
Or Google could leave it the way things are and receive a constant flow of stories about malicious apps on Android.