I think your basic approach is correct — as you noted, there are several really useful things that you can do with a bitmask for your countries, and especially for things like picking there really aren't substantially better ways. But it sounds like you're looking at the construction of these masks backwards; rather than building individual masks and carefully fitting them together jigsaw-style, I would go the other way: start with a bitmap of the map as a whole, either a single black-and-white layer where the black pixels represent boundaries or a full-color image that has a specialized 'boundary color' for doing the same thing. It should be easy to tweak your pipeline to make sure you can generate an image like this; it's almost a necessary piece of building the full-scale worldmap, and should be at worst be an easy by-product of the art generation process.
I'd suggest building a small tool that can take this 'map layer' and create the bitmasks you're talking about: do a linear search through the bitmap for a non-boundary pixel, then floodfill from that point with respect to the boundary pixels, marking off each pixel that you fill in a second bitmap. Once you're done, that second bitmap will be the mask for one territory; you can clip it to its minimum size (keeping track of where it came from in your original image), fill its pixels in your original image so they aren't considered again, and then do another scan to look for non-boundary (and non-filled) pixels. Continuing like this will eventually give you all of your territories, along with their positions in the original map, and from there everything should work like you were outlining.
Note that the key to this process is really the tool — having a mechanical process that can work from a relatively easy-to-produce asset (in this case, the overall map) and give you the assets you really need.