You can have a central process which controls the player starts. It builds an array of all player starts with GetAllActorsOfClass. When a player starts, the call a function on this process which returns the next useable player start from the array.
If the player starts need to be from where the player was previously, then you need to store the array of player starts in the savegame.