Isn't this a causality paradox?
Yes. The next paragraph I will write will kinda be a spoiler, so don't read it unless you really want to know my opinion which may also be the answer.
First of all, when you meet the Windmill man in the future, it hints towards you that you shall go back in time and play the song again for him. Doing this will open access into the well, so you can get the Lens of Truth, which is important to progress through the game.
So, how I see it, there is no answer to this. There are options, but they are practically denied by parts of the game. Like this theory:
As Link moves forward in time, he duplicates, leaving one copy in the past, and one in the future. As YL (young Link) does his in the past, it changes the way the future is laid out. So older Link learns the Song of Storms from the Windmill Man, and goes back to the past and plays it for him there, as YL is deleted due to OL going back before the duplicate was created.
ENDED due to giant spoilers, lolz.
What denies this theory is that from what I remember, (I haven't played the game in a while) is that Sheik or whoever says to Link that he is the Hero and that he has been sleeping in the ToT for 7 years. This ruins the theory above, which I mean is a pretty good theory. Come back when you have finished the game, and I can explain the theory further.
The song was made by Flat and Sharp the Composer Brothers. Although they lived in Termina, young link learned it there then went back on his quest in OoT were he played the song in the Windmill. Then, Guruguru teaches you the song in the future again. It is sort of a paradox, but it makes more sence than it seems.
Sorry dude, timeline theories denies it. [IMO, and I think it makes sense]
[SPOILERS]
As Zelda sends Link back to his own time, Ganondorf is sealed in the Twilight Realm, because Link (who has started his adventure) tells Zelda about Ganon, because Link's memory is not depleted. Zelda warns the Sages, who seal him there. (TP logic) Then Link wanders off to Termina, and goes on his own little adventure. The whole 'Zelda sends Link back in time' creates the split timeline.