Really recommend GIMP. Have used it since college, like 10 years now. Once you know how to use its tools, doing exactly what you want would be dead simple.
If I grok at a glance what you want, it's basically what I did to create this:
http://www.bay12forums.com/smf/index.php?topic=136638.msg5035603#msg5035603As far as tutorials....with GIMP I've generally found I can figure out most of the basic stuff, and I google for tutorials specifically related to what I can't figure out.
But here's some really useful things to google/tools I use all the time:
-Fuzzy Select Tool
-Invert Selection
-Paths Tool
-Selection From Path
-Stroke Path
-Basically everything under the Image/Layer options at the top.
And absolutely, positively Google for some tutorials on using Layers. I went years being too lazy to learn about them, and using Layers made GIMP twice as easy to use. Also, CNTRL + Z to undo if you don't already do that. Which after all that effort you put out above, you probably do.
Funny story about GIMP. When I was in college doing visual design and photo editing, my professor came over to see what I was doing, and noted the program I was using wasn't anything they'd showed us how to use in class. He asked what it was and I told him the name. He heard it and looked at me like he was about ready to kill me. I should mention he's a Vietnam vet who'd lost his hand and had a metal grasper claw replacement. Thank god I knew what the acronym stood for, and rattled it off like my life depended on it.