It's possible to define random colors in .kml files. Make Marble calculate suitable values and display them.

Random colors (as per colormode=random) are already read from kml files and available in GeoDataColorStyle. Extend it to implement a QColor paintColor() const method which returns, acoording to the colormode, either the original color or a randomized color. Randomized colors need to be calculated according to the kml spec, see https://developers.google.com/kml/documentation/kmlreference#colormode