Jack has an online randomizer I use pretty frequently, although he hasn't worked on it for awhile.
I requested a feature to randomize starting provinces (random commander, random units, occasionally random items) and since we both liked to play that way he put it in. It works moderately well, although I think its tied into start/specstart commands so it depends on the .map file. Probably wouldn't be too difficult to modify it to be a bit more thematic or use a smaller unit ID pool.
Pretty cool, sometimes you start with a random myrmiddion with 10 chaff and sometimes (once) with a lord of hell and 10 succubi troops (no abilities). The AI gets the same benefit, although I'll usually restart till I get something good and have no idea what they get
Unfortunately never played the lord of hell one, terrible position.
I think its at
http://dominions.realites.org/