I suppose you could be limited by whatever platform you're using, but I have implemented almost the exact same concept in Cocos2d, which was fairly simple. Basically you created a specially named slot where the rider attaches and then add the rider's skeleton as a child of that slot ( in code ). Draw order should just work itself out, though that will depend on your platform/engine.
If you want to batch the entire composition, you'll need to (practically speaking) dynamically batch your textures together, unless you have a small number of horses/riders in which case you could probably fit them all on one sprite sheet.
I'd recommend tackling the composition first, then worry about batching (which is just an optimization) after that is working to your satisfaction.