¿Es posible permitir o negar el acceso a internet a cada aplicación independientemente?

Sí, es posible.

Yo tengo Miui y esta capa de Android me permite hacerlo sin necesidad de bajar ninguna app, pero creo que con android puro, necesitas bajarte alguna aplicación que actúe como un firewall (DoridWall, por ejemplo).

Vaya, parece más sencillo de lo que pensaba. Solo hay un problema: la mayoría de cortafuegos que he visto requieren tener el teléfono rooteado. No descarto hacerlo en algún momento (sobre todo porque parece ser la única manera de instalar aplicaciones en la tarjeta SD, cosa que me hace mucha falta teniendo en cuenta que mi Samsung Galaxy Ace GT-S5830i solo tiene 200 MB de memoria, lo que me parece poco menos que un fraude, pero eso es otra historia), pero ahora mismo no me apetece mucho complicarme la vida. El único que he visto que no requiere rooteo es el Mobiwol. ¿Alguien lo ha probado o conoce algún otro?

Si quieres ser root, hay programas tanto en el pc como directamente en el movil en el que pulsas un boton y ya lo tienes

¿que móvil tienes?
PD: acabo de ver en tu otro comentario el móvil que tienes.
Pues algo escaso de memoria andas, ya nos cuentas que haces al final.
Suerte.

Hay firewalls que funcionan sin root, busca un poco y los encuentras.