It can be done, but as you say it would be challenging. The first thing I would suggest is decide the limitations.
I mean, if you are going to conquer the world, then a static map would work with territories, etc. Procedurally generated images, especially if you are dealing with terrain, not so much. Yes, you could stick with descriptions, but a lot of people would immediately be turned off by text only…though there were some games from the early 80s that also had similar elements.
This leads to the other problem: interface. I mean, in most 4x Games you click a territory/image, you are there. In the case of a Choicescript, it would be ‘press here to interact with this place’. I know some players could get a kick out of managing 50 territories but most wouldn’t. That goes back to the limitation thing.
Things like upgrading, building locations, moving armies, etc. can actually be done fairly easily. Hell, look at Zombie Exodus Safe Haven as a way to do upgrades, etc. Multiply this across territories, etc.
The funny thing is that there are other things that could be easily implemented to hopefully keep things fresh.
For example. you could create a list of random things that happen. If you go for a territory manager, I could easily create 100 ideas for random things that happen (bandit attacks, weird ass weather, etc.)
You could probably even have a random npc generator if you go whole hog with marriage proposals, etc. from the other side as well. Not that these would be very deep.
And yes, I realize these are also elements in other games. And yeah, these are some ideas I had for a game with similar elements in RenPy (biggest use for it is visual novels, but others have made old school point and click adventure games, etc.)