(Difficulty: Incredibly Easy): If you're in Developer Mode, many of the restrictions in place to keep you safe are missing. This makes it easy for developers to test apps, but makes the device incredibly insecure. Thankfully, turning on Developer Mode is non-trivial in newer versions of Android (just a few years ago, it was not much more than a checkbox in the main settings menu). This mode should always be disabled on hardware that contains any data you care about.
(Difficulty: Easy): If you allow installs external to the Play Store, it's possible to spoof permissions due to various glitches in the permissions API. Without using the Play Store, your device can install non-Google managed software, including malicious software that can be linked to from a normal URL. It's also possible make a "no-permissions app" that later elevates its permissions through a stack overflow/underflow or buffer overrun/underrun exploit. I don't know of any specifics about those types of vulnerabilities, but I would presume that such attacks are possible.
(Difficulty: Moderate/Dependent): Some devices are "rooted" by the user, which is necessary to install some classes of apps that are not ordinarily allowed. This bypasses many of the restrictions that Linux provides, because the user is now logged in as "root", giving superuser access to the user and all apps that they install or run. Many people don't realize this is a bad idea, and so are later surprised to find out their device was compromised simply because they gave the primary user account elevated privileges (translation: they didn't know what they were doing, and what the risks were).
(Difficulty: Hard): Otherwise, if you're not in Developer Mode, and you're not allowing external installs, and you haven't rooted your device, there are vulnerabilities that exist in various scripting engines that are used by the Play Store and other apps. These can be exploited through UXSS (Universal Cross Site Scripting) attacks, where the main installation intent is invoked without the usual permissions dialog, and the only thing that's necessary is loading the script in memory through a link in a message or email. For example, Android Jellybean and lower could be hacked this way. Never trust links from sources you don't trust, and consider installing security software to reduce the likelihood of unwanted installs. NOTE: As far as I know, most apps automatically attempt to invoke an intent rather than check for some arbitrary notion of security. That is, the browser doesn't know if you meant to install an app, but it looks like you did, so it sends this request to the installation intent/Play Store.
Note that this isn't unique to Android, as iOS, Firefox OS, and Windows Mobile all have potential vulnerabilities, especially if "rooted" or otherwise modified than ways that were intended. It's also possible that carrier-provided software (those annoying apps you can't uninstall) could also have vulnerabilities, and you might not even be able to uninstall or disable those apps.
