According to Encyclopaedia WoT, construction of the White Tower started in 98 AB. Furthermore, the breaking itself lasted something like 300 years. Hence, it seems entirely possible that at least a few Aes Sedai who were raised during the Age of Legends were still alive when the White Tower was founded. And if not, it seems unlikely that the group of women who created the tower had grown sufficiently large and powerful if they had to start learning channeling from scratch, so it's a reasonable assumption that there is an unbroken chain of women teaching other women to channel that leads from the Age of Legends to the founding of the White Tower, and from then on there has always been Aes Sedai living in the tower.

So how did Travelling become a lost Talent? It seems to be one of those things you don't have to have a particular skill to do, just the neccessary strength. Even among the regular Aes Sedai of today, quite a few are strong enough to Travel, and strength seems to be at an all time low at the moment, seeing as Cadsuane was hailed as the strongest in centuries when she arrived.

It just seems to me that Travelling is such an insanely useful thing, in particular during the breaking when a quick escape could be handy at any time, so why wasn't it taught to every student as soon as they were strong enough?