I'm working on a Civ II modpack/scenario. The game is takes place on the cultural area of the British Iles and spans the time period form about 600 AD (post roman) to 1300 AD (end of feudal age, gunpowder used). It has a fantasy setting, but the Tribes are borrowed from history.

The following is the list of tribes I have chosen to include. Civilizations in the same row cannot coexist.
Britons Mercians York
Angles English Wessex
Northumbria French(Frankish) Normans
Irish Dalriada East Angles
Welsh Strathclyde Saxons
Vikings Kent Jutes
Scots Picts Danes

I am in need of online resources that would help me find a list of cities for each of these, as well as a name for the male and female rulers. Because this is a fantasy setting, the names can be mythical but they must be from the time period. So far I've mainly been using wikipedia.

Well a good place to start is the Doomsday books obviously- they contain lists of names and places for everything. They can be found online these days as well. Though that is only from 1070ish, i think it would be a bit of a struggle to find one condensed thing for the british isles before that as we weren't so hot on writing stuff down back then.

As for leaders of the places you could try looking at medieval total war, viking expansion. I believe they originally had a few factual leaders.

I wouldn't trust Wikipedia on this (or indeed on much). I made a Civ III scenario on precisely this time period and spent ages getting the city lists, leaders, etc as exactly right as I could, so the best resource I can point you to is that scenario, which is linked to in my sig.

So far for Doomsday, I've only found an ability the ability to verify if a place is in it, but no list of places available without purchase.

Unfortunately I don't have Civ III Conquests, so I can't look at the scenario.

souron,

you might want to have a looksee here:
http://www.the-orb.net/
a great site for medieval studies (social, political, etc)

and within HERE (http://www.the-orb.net/encyclop/culture/towns/towns.html)
lots of great links and data here....