Verin knows how important the Aiel are to the Light; she's studied the Prophecies of the Dragon, which strongly imply that the Aiel will have a central role to play in coming events, and she's also studied Dark Prophecy (she tells us that all the way back in TGH), and the Light only knows what those might have to say concerning the Aiel. Verin has plenty of motive to want the Aiel to get it right. The best way to affect the Aiel is through the WO's... and the best WO to affect is the one connected to Rand.

Verin knew of Aviendha from Verin's time as a WO apprentice after Dumai's Wells, when Verin and Avi were both WO's apprentices in Cairhien at the same time. We know that Verin knows at least a little about Dreamwalking, because she gave Egwene the twisty ring terangreal back in the way back, and she's read Corianin Nedeal's notes. Verin also knows about Aiel culture from being immersed in it during her captivity. She might not be able to get away with pretending to be Aiel for a long-term stretch, but she's more than equipped to fake her way through a single short conversation. Especially when the mark doesn't suspect anything and isn't on the lookout.

Everybody in Cairhien knew that Aviendha and Rand were close, and therefore anybody who's looking for leverage over Rand and has two brain cells to rub together would want to find out as much about Avi as possible... and Verin has a lot more than just two brain cells. Verin's involvement as a WO apprentice while Avi was also a WO apprentice, (not to mention Verin's access to DF eyes and ears... the Aiel count DFs among their number, too), make it entirely likely that Verin knew Avi's life story by that point.

Beyond that, process of elimination rules out most everybody else. The funky tricks that Nakomi works make it pretty evident that she must be channelling, and since Avi senses neither the flows nor her ability to channel, she must be hiding both. That rules out the WO's; they know how to invert their weaves, but they don't know how to hide their ability to channel. The Sea Folk and Kin are ruled out for the same reason. It could be an Ashaman - it's possible she senses nothing because it's saidin - but what Ashaman would bother? An Ashaman might know of Aviendha's importance to Rand, but no Ashaman knows the location or significance of Rhuidean. Plus, the encounter is a lot more benign than one would expect from an Ashaman, even a good one. It also much too benign to have been one of the Forsaken, who would have simply scooped her up and hauled her off to Shayol Ghul for questioning. The only group of channelers we haven't ruled out yet are the Aes Sedai. For the reasons you said in your post, it had to have been someone who knew a good deal about the Aiel. That rules out all the AS except the ones who were captured after Dumai's Wells and forced into apprenticeship, and Egwene. Egwene has an alibi, as she's imprisoned in the Tower at the time. Out of the rest of the apprentice AS, two are with Perrin in Ghealdan and accounted for, a handful are with Cadsuane and also accounted for, and of the handful that are left, none had any motive to help the Aiel. Except Verin.