To avoid it being messy, and to make it easier graphically, how about having prebuilt roads, but they start out as dirt paths. Then the user gets the option of upgrading the paths to paved roads.

I'd make an overlay with a greyed-out or reddish color coding of where you can build roads. For the purpose of keeping it open, some of these roads should not directly connect to other cities, but to "hubs". When creating the first road that connects two cities, make the hubs appear as well, but make sure other roads connect using the same hub (avoids visual clutter).

Should be fairly simple to implement that way.

As Orymus3 said, hubs are a valid idea. Let's look at this - several villages are able to connect to one bigger town that will act as a region capital. Each village can have a direct connection to the other and must have a connection to the region capital, be it direct or through another village. From that point, you can connect region to region with the connection points being the corresponding region capitals. A village in one region cannot have a direct connection to another village in another region. The way to get from that one village to the other should be through the region capital.

There are other ways to solve this problem as well. I would strongly suggest you look into some graph theory. With a proper understanding of graphs you should be able to solve a big lot of logistics problems as graphs are the actual thing used for real world road works and logistics.

There are other ways to solve this problem as well. I would strongly suggest you look into some graph theory. With a proper understanding of graphs you should be able to solve a big lot of logistics problems as graphs are the actual thing used for real world road works and logistics.

One important thing, it is the PLAYER's job to solve these logistic problems That's where the fun is (how to lay down the road system properly).

That's why I'm not so fond of hubs... It's the player that should "invent" that there should be hubs (or maybe if there should be not in a particular map). The system should allow the player to have fun with laying down these roads, optimizing what route would make most sense and so on.

With hubs it's trivial (no decision to make), all neighbouring villages are connected to the nearest city and that's it, all you can do is upgrade these roads.

You've got a point. However, if the player is to be free and as creative as he/she wants, then you always have the possibility of having messy logistics. Having the clean roads would imply restriction, at least to some degree. In that sense, you can maybe combine some stuff ? Since you do have the village positions preset, you can, as LorenzoGatti suggested, limit the crossings to a certain ammount. If you have designed the villages to be structured into a closed graph with the sufficient ammount of weight on each village, as a point, you should be able to build a road from any one point A to any one point B in the same graph. That does imply though that these connections are not going to be direct most of the time and that you will most probably need to go through a point C in order to reach point B. In that case, the road might not be as efficient as possible, however it will exist. By doing so and having the ability to cross an N ammount of times (N being the number that suits your needs), you should be ok and have a somewhat not ugly logistics system, without limiting the player too much and without having separate villages isolated.