I always am able to complete the Gerudo Fortress once I get the bow. How did he get into the Fortress as Young Link? My computer can't display the video.
With glitches it's a cucco jump (search and i'm sure you'll find something on youtube). And I believe I read somewhere that the gerudo pass can be obtained as a child (only with using the cucco jump or other glitches though).
Without glitches it is only possible in the N64 version because the river of sand could be walked over at the edge with backwalking (unless you consider this a glitch also).
1. Warp to Spirit Temple
2. Walk through the Haunted Wasteland (must have the path memorized since the poe doesn't appear at that entrance to the Haunted Wastleland)
3. Cross the river of sand by backwalking across the sand on the edge on the side near the flying carpet salesman.
4. Since you warped to the Spirit Temple you probably already got the gerudo pass as adult link so you can walk around freely. I do not know if you are allowed to enter the training grounds by talking to the guard as child link (I would assume you are though). But with glitches virtually everything is possible so I would guess you could get in there anyway.
As for the topic, I'm 99% sure you can get it before entering the Water Temple, maybe even earlier.
As Caleb said you need 7 of the 9 keys. In this paragraph I'm using the names of the rooms given by the ZD walkthrough. The keys in the sandy stalfos room, dinalfos room, and room of locks require no dungeon items so that's 3 easy ones. The key in the lava room just requires the song of time and no items. You can collect all the silver rupees in the lava room without the longshot to open the water room. The water room just requires the iron boots (the longshot and zora tunic would make it much easier) to get the key. Go through the lava room to the flaming enemy room (the door is elevated so maybe you can't reach the hookshot target without the longshot, but you can hookshot the torch below it), and you need the megaton hammer to get the key. You need the megaton hammer and bow to go to the eye statue room from the flaming enemy room. The eye statue room just requires the bow for the key that appears in the platform in the center of the room. That's seven keys and enough for the ice arrows. I purposely went through this path because I think (very unsure) that you need the longshot to pass through the timed silver rupee room. Also I'm not sure if you can reach the second platform in eye statue room without the longshot to reach Pierre to get the key through the door there (but this would be the 8th key so it's extraneous for the purposes of my path).
So anyway, it's definitely possible to get the ice arrows with the bow, megaton hammer, and iron boots without the longshot. It might require even less than that though, I'm not sure.
Thread moved to Game Help.
I usually never get the Ice Arrows when I play through OoT, but as Bellum said, you need the Silver Gauntlets in order to complete the Training Grounds. And I seriously don't know if you can beat the Spirit Temple before the Water Temple.
Since you only need 7 of the 9 keys you don't need the Silver Gauntlets to get the ice arrows.
You can definitely finish the Spirit Temple before the Water Temple though without glitches. My explanation depends on your definition of a glitch and the version of the game you are talking about. In the N64 version you could backwalk across the river of sand so you could reach the Spirit Temple before entering any other adult dungeons (you just needed Epona to jump Gerudo Valley and I think the hookshot also to freeze guards in gerudo fortress). You do need to beat the Forest Temple in order to be able to go back in time to beat child Spirit for the Silver Gauntlets though (in a glitch free run).
You can also (in either game) complete up to the longshot in the Water Temple, leave, beat the Forest Temple, then beat the Spirit Temple. So technically you can beat the Spirit Temple before beating the Water Temple, but this way of doing it requires you to enter the Water Temple before doing the Spirit Temple so it kind of defeats the purpose.