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 Deku Stick using Quick Draw.
If bombchus are readily available, it is possible to do a Megaflip over the gate. It should be noted that one cannot pause buffer "speaking" or "reading". Due to the proximity of the Gerudo guard, trying to press A to roll from this position would result in Link talking to her instead. However, if you pause-buffer the A press then Link will roll as intended. One can position for the Megaflip as shown in the video, or target the gate and pause buffer a backflip and turn around.
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 will encounter is the river of sand. Go to the far left side of the sand, and backwalk over it at the edge to cross it. When you get to the top immediately stop or sidehop to avoid hitting the kill plane and being sent back to the start of the Wasteland.
From there 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 Sheik as child). Inside you can get early bombchus and Silver Gauntlets - useful for skipping Saria's Song and the Goron Bracelet.