¿Existen aplicaciones sandbox que no requieran que el teléfono esté rooteado?

Eso sería una contradicción en los términos: Para deshabilitar los permisos sobre la marcha, se requieren permisos de root - no hay manera de evitarlo.

Para los usuarios que no son root, sólo hay un enfoque diferente: Tomar el .apk antes de la instalación, manipule el Manifest (eliminar las solicitudes de permiso no deseadas), volver a montar el .apk y luego instalar el paquete modificado. Efecto secundario no deseado: No hay actualizaciones directas, ya que la firma del paquete se rompe de esta manera. Una aplicación que hace esto es, por ejemplo apktool disponible para Windows, Mac y Linux.