Murcielago
I've just set up and tested it again in two different profiles:
Profile 1 (Sandboxed Google Play)
Profile 2 (without GSF, GPS and Play Store)
Profile 1: The workaround described here with short-term network access works fine.
Profile 2: Workaround does not work. The only available tool under Edit>Tools remains beeing Magic Eraser.
So the reason seems to be the missing of Sandboxed Google Play.