Maybe for the situations where you have to go and she doesn't, you can still send her into the female restroom to wash her hands, comb her hair, or just "try" to use the bathroom. That way she is contained somewhere that both of you feel comfy with her being, and more than likely, you will be done first. Tell her to stay in there until she hears you call her name when you are done.
FWIW, there are benches right outside almost every bathroom. I just park my kid there with strict orders to not move. Nobody bothers them, etc. I understand your worry, but I would bet if you try it once at WDW (like you park her there, and you just run in and wash your hands...back out in 30 seconds), you might find it a lot easier/less worrisome than you thought. Just ease into it. Hard, as a parent, to take those big steps towards independence. WDW is a good place to start the process with baby steps!