"Marty, you're not thinking fourth-dimensionally!"
When Link goes from the past to the future, he is transported to a version of the future in which all the dungeons that he's completed as a child are complete, including Bottom of the Well. Because the Bottom of the Well must have already been done in the past, that means the Song of Storms must have already been played in that realities version of the future. The only reason you have to go there at all, is because otherwise you won't have the items from those dungeons, not being the Link who completed them.
The Link who originally plays the Song of Storms is not the same as the Link you control. He's the Link from THAT timeline's past which mostly parallels your own, not your own past. The difference is, that Link didn't make it past childhood for some reason. And in that timeline, either Link was more mischievous and invented the song, or the song existed somewhere in Hyrule (perhaps the Composer Brothers in that timeline wrote the Song of Storms instead of the Sun's Song, because they were trying to influence the weather instead of time).
After you play the Song of Storms as a kid, you recreate the same circumstances on your own timeline that allowed the other Link to access the well.
The question lingering in your mind is probably, "Well, what about the Magic Beans? They're only present in the future if you plant them in the past." This is going to get a little bit hairy, but bear with me. The magic of the beans somehow allows you to influence your counterpart on the timeline you visit in the future, that exists parallel to yourself, to plant a Magic Bean in the same place. Though the timelines are separate, magic on one can somewhat influence the other.
I consider this plot hole fixed. ^^