An when he gets to heaven
To Saint peter he will tell
"One more marine Reporting sir...
I have served my time in hell"
I think that would work better with Inkscape or Illustrator. You could do it in Photoshop with some layer-styles though. A tip on the regions: for each region, create a layer as a colored mass on that layer (1 layer for each region). Then set the layer transparency to something like 70% and add in a "stroke" layer style a few pixels wide of the same or a complementary color.
Hey, great! Let us see how it turns out!