I think the essential problem with road spamming in civ4 is, there's nothing else for the workers to do at the end. So they end up road spamming to places that are nowhere.
So how about workers being able to become population. If I remember correctly, I thing this was possible in civ3. This does unlock a strategy where you can make a dozen workers before making a new city. But this would be very costly in an early game anyways, the only time there's any extra land to make new cities. A possible solution for the endgame is having workers upgraded at a certain tech to be very expensive (the upgraded worker being faster like the indian worker, but only the same effect for becoming population). Players are tempted to convert workers into population after having them build what is really necessary.
And about being able to use enemy roads: well think of it this way, if you know the enemy is going to be able to use your roads, you won't build roads in places you don't need and the enemy might use. You would probably build many roads in the center of your empire, while having few roads by your borders. I would imagine myself building a hill-fort and having country-border-road go through it. Connecting cities with multiple paths will have their merits and demerits: it will be harder to cut them off from the rest of your empire, but the empire itself will be vulnerable from mobile units.
But I still think the AI won't be able to use all this as well though.
Interesting thing to think about
So how about workers being able to become population. If I remember correctly, I thing this was possible in civ3. This does unlock a strategy where you can make a dozen workers before making a new city. But this would be very costly in an early game anyways, the only time there's any extra land to make new cities. A possible solution for the endgame is having workers upgraded at a certain tech to be very expensive (the upgraded worker being faster like the indian worker, but only the same effect for becoming population). Players are tempted to convert workers into population after having them build what is really necessary.
And about being able to use enemy roads: well think of it this way, if you know the enemy is going to be able to use your roads, you won't build roads in places you don't need and the enemy might use. You would probably build many roads in the center of your empire, while having few roads by your borders. I would imagine myself building a hill-fort and having country-border-road go through it. Connecting cities with multiple paths will have their merits and demerits: it will be harder to cut them off from the rest of your empire, but the empire itself will be vulnerable from mobile units.
But I still think the AI won't be able to use all this as well though.
Interesting thing to think about
and 
.
