Rabbi Yochanan said no woman had engaged in intimacy with someone who had been circumcised from eight days other than Rivkah. Reish Lokish said, since the daughters of idol worshippers guard themselves from nakedness and abandonment from another place but this virginity (i.e. that of Rivkah's) was purely from a place of virginity (i.e. and not of any pagan ritual). "And no man had known" - i.e. from another a place. Rabbi Yochanan said it is implied from the fact that it says that she is a virgin that we do not know and no man knew, even no man had a 'claim' on her like it says (Psalms 125:3) "The sceptre of the wicked shall never rest etc."...
So we see three reasons for this calling out of Rivkah's virginity:
She was the first to be with someone who had received Milah at the correct time.
Her virginity was due to her absolute pure character and nothing like the pagan practises at the time.
"No man had known" means that no one had even asked for her, as the passuk in Tehillim implies that the righteous are protected from the wicked.