At least one faction *does* have a supply unit: the Fay Boar. Nature mages provide supply, as do some Gods (the Great White Bull and Lord of Fertility are the only ones I can think of).
And you already know some of the nature items - the Enormous Cauldron of Broth (Cons 2, 20 Nature, 50 supply) and Endless Bag of Wine (Cons 4, 5 Nature, 25 supply). There's also the Summer Sword (Cons 4, 10 Nature 5 Earth, 50 supply). But that one's a little harder to forge - the other two can be forged by a Druid (possibly with a Thistle Mace, but he can forge that himself and you only need one). The same commander (or scout) can carry one of each for 125 supply - not counting any nature mages or fertility gods you may have with you.
Supply caravans are already represented by fortresses providing supply to distant provinces. IIRC this is based on the fort's admin values, so a Fortified City will indeed give you fewer supply headaches - until the front moves and you have to build another one. Then the tremendous gold cost of the FC will keep you from buying too many troops.
I don't think the game needs any more ways to supply armies. It's already hard to starve out forts because the defenders usually have nature mages or supply items, and even large armies can be fed by items and/or nature mages. Bags of wine are one of the most gem efficient ways - there's no reason they couldn't be carried by your army commanders instead of scouts, unless you routinely fill every item slot on run-of-the-mill commanders.