Some of the most fun I've had writing code in a long time was doing something similar, but much simpler. My basic approach was to start with an existing coastline shape and just make more-or-less evenly shaped polygons inside of it. Example:

http://victorsunited.com/map/South%20Pole/board_game_rules

I didn't do any biome coloring or similar because the game displayed colors on the map to indicate which player was occupying it.