I recently played Armies of Exigo. It may be worth downloading the demo and playing it as it has some similar elements to what you talk about. If for nothing else to see how someone else has tried to do something.
You also mentioned some features it does not have.