I did that once by picking a bunch of random locations on the map, and then picking the location nearest each start location.
In other words, each of the 9 start locations are predetermined, but they are only used to pick the nearest random location.
In my case it placed a bunch of castles at random, and then picked 4 that were nearest the corners for 4 players start locations.
("Pick Nearest/Furthest" is under "Size & Position" in the object's conditions)
You could also use the "Distance" expression to make sure they aren't too close together as well.