In Gerudo Valley grab the cucco and walk to the gate guarded by the Gerudo in white. To the right and left there are small posts jutting of the bridge. Stand on top of the left one carefully walk to the very edge of it. Now turn around without moving and face the Gerudo. Carefully position yourself so that the left wing of the cucco meets up with the right side of the Gerudo. Run forward, and just as your about to jump off the post hit left. You should get a full jump towards the middle-left of the gate. Moments before you hit the gate, press B to jumpslash. This should be just enough to reach the other side of the fence. You're not done yet though, as the guards can still catch you and chuck you into the river. Just make your way to the fortress.
This is also possible with a stick using quick draw.
If bombchus are readily available, it is possible to do a megaflip over the gate, where a cucco would otherwise be required. It should be noted, that one cannot pause buffer "speaking" or "reading". Due to the proximity of the Gerudo guard, trying to roll from this position would result in talking to her, but if you pause buffer it (press A only a single time during the unpause lag) then you can roll instead. Line up using tips Link's feet in relation to the edge of the plank of wood on the bridge as a reference.
Outside the Fortress stands a large wooden gate, blocking the path to the Haunted Wasteland. Thankfully, there's a very easy way around it. Climb to the top of the ladder next to the gate, then turn back and use C-Up to turn about 45 degrees right. From there simply sidehop left to the mountain to your left, which is normally unreachable. Just move along the wall until you past the gate, then sidehop back in bounds to continue on into the Wasteland.
The first thing you'll encounter is the river of sand. Go to the far left side of the sandtrap, and backwalk over it at the edge to cross it. When you get to the top immediately stop or sidehop so to avoid being sent back to the start.
From there just follow the flag poles until you get to the shelter. If you have the Lens of Truth, you can continue on normally. Otherwise, you will have to memorize the rest of the path. The video below shows how to do this.
Then just get through the Desert Colossus without getting killed and enter the Spirit Temple. You can get the Requiem of Spirit by leaving the Temple, giving you quick access to the temple (and cause a time paradox by meeting Shiek as child). Inside you can get early bombchus and Silver Gauntlets, useful for skipping Saria's Song and the Goron Bracelet.