Would it be possible to sandbox apps with SELinux?
Android already has this kind of sandboxing of apps. Each app gets its own data directory (and optionally another on the SD card), and only that app can read that directory. Apps can't read other apps' directories directly.

When an app (such as the gallery) wants to make its content available to other apps, they can offer an interface for the other apps to use. In fact, there are two kinds of interfaces apps can offer.

The first is via the intent mechanism. This is used when you get (for example) a "Choose image from" dialog, with different apps to choose. The intent mechanism allows the app that owns the image to grant the calling app temporary access to only the image(s) you choose this way.

The second mechanism is for the app to act as a content provider. The app then acts like a server, allowing other apps to browse and find content, and access it directly without your interaction. When an app acts this way, it's up to the app that owns the content to choose what security mechanism to use. The app might require that the calling app have a particular permission (even a new permission specially created for this purpose). For example, access to contacts is provided this way. Only the built-in contacts provider app has direct access to the contacts database. It also acts as a content provider, to allow other apps access, but only if they have the appropriate permission (such as "read my contacts").

So, as you can see, the mechanism you describe - to sandbox apps, and to pass files from one app to another only through the user's choice - already exists in Android. It's way ahead of desktop operating systems in this respect. It's up to apps to use these mechanisms to control the content they own - and there's always going to be a trade-off between granularity of control (using lots of permissions) and making things easier for the user to understand (using fewer permissions).