Lasso tool might be a little rough for clipping them out.. but i suppose it could work.... It's really best to build your map that way to begin with (0: (dont you hate that kind of advice) ha
Actually, you might want to try Inkscape out. It is vector based and would probably help you with drawing borders as well as placing text.. and most importantly.. anything you do in vectors can be scaled without data loss or pixelation. You should be able to bring your map into the program on a layer. I use Illustrator so I haven't used Inkscape for a long time.. i just tried to open it to see if i could offer you more advice but it doesn't want to run on my mac anymore. I'll try it out on my pc tomorrow and see what i can find out.