As many have said, pre-colombian America is the right example of horse-less army. Don't underestimate the Incas - they have made quite a valiant stand against the conquistadors, not like their wussy cousins from the north.
Horses are simply most effective in what they do, but they are not the only things that can do it. Anything that is fast, thin and can carry a man on his back can be used. People ride ostriches, you know :)