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/