I can think of a few solutions:
Maintain a vertex array for each different texture. Even if there are 10-20 different textures then drawing this many arrays is negligible. If a province needs to change texture, rebuild the array it was in, and the array it needs to be in, moving the province vertices from one to the other, and thus changing the texture.
Use some shader magic. This wiki page explains how multiple tiles can be drawn using a texture to look up tile indices:
https://github.com/SFML/SFML/wiki/Source%3A-ShaderTileMapWith some work, as long as you don't mind losing the ability to colour your vertices, it could be modified so that the vertex colour is used to select the correct tile, rather than using a lookup texture. Then at runtime changing the colour of the vertex would select the desired tile.
Use some shader and OpenGL magic. Probably over-engineering, but expanding on the previous suggestion you could use a
texture array. Then, using the vertex colour property again, you could select the appropriate texture by indexing it via the colour value.