Besides Rand and birgitte, do we know (or suspect) any past embodiments of other characters?

I'm pretty sure that Matrim Cauthon is a rebirth of one of the Kings of ancient Manetheren. Quite besides the memories he got from his second visit to the Aelfin and Eelfin, he quotes the Old Tongue quite at random under pressure, when under attack from Trollocs and Fades before they reach Shadar Logoth, and in the Blight, while being healed and disconnected  from the Shadar Logoth dagger, and in Tear while gambling with those Disreputables, the young Lords.

I don't think there are any definitive cases of specific characters being reimbodied (other than those you have mentioned and the obvious cases of forsaken coming back).  

There is a case to be made the Elayne is Ilyena or that Egwene is Lutra, but both of those are basically just on the foundation of the parallel roles that those characters play in their respective timelines, particularly as they relate to the Dragon.  That and Elayne maybe looks like Ilyena and has a similar name (although similar physical appearance and name aren't always required for reimbodiment anyways.  Rand doesn't really match the [admittedly sparse] description of LTT, for instance).

 

Mat may be someone from ancient Manetheren, as mentioned, but the explanation that he just has the blood of Manetheren is also reasonable, if not well explained.  

RJ has said it's very rare for souls to always be playing major roles, most the major players will be different souls next time.  You look at the heroes tied to the horn and see most of the souls tied to the horn were missing the Last Battle.  The Forsaken will be different etc.  Since it would kill the free will if the forsaken were the same every time, it would also mean souls could be perm evil.  So most of the major players this time are just people who got lucky this time, but next turning they could just be ordinary people during the Last Battle.

Also numerically it is unlikely that anyone alive during the books has had more than one other rebirth since the age of legends.  Immediately prior to the war of power the population would have been similar to our current era (billions alive at once).  The population at any time since has been far smaller - tens of millions (so 1% or less that of the AoL).   3000 years or so and an average lifespan of 30 years would allow about 1 rebirth each unless a particular tied heroic soul was reborn for particular purposes.