Вдумайтесь, Android assigns each application a UID (User ID) at install timе.
… at install timе.
Вы предлагаете при инсталяции прописывать каждое приложение в /etc/sudoers?
Зачем? В андроиде пользователь уже итак раздаёт разрешения через его АПИ.
Или при каждом запуске предлагать подтвердить эти права (как в виндовом UAC)?

Это не поможет, т.к. смысл сабжа в том, чтобы при разрешении приложению функций А, он ещё параллельно не выполнял не декларируемые им функции Б, В, и Г, т.к. разрешения на А (допустим А это права root, пусть через sudo) дают такую возможность, но заявленная функциональность приложения не должна выполнять функции Б, В, и Г. (к примеру Г — это чтение хэшей из /etc/shadow, как skype в своё время).

Т.е. вы даёте права root приложению чтобы он к примеру обновил резолвер dns, а он параллельно с этим слил ваши хэши в АНБ.
SELinux позволяет эти действия прекратить.