Well, jeeze I can't be the only person who does minor encounters without breaking out the minis and the battlemat.
Largely it plays in feel much like second edition. The DM estimates how far away people are from the combat or who would be hit by a spell effect.
The best rule to consider is "combat advantage" for mini-less play, because the position of the mini is largely to show whether someone has combat advantage. If you are describing a cinematic scene, then the player can generally describe getting to a superior position.
The other reason to have minis in 4e is to decide where and who the area effect spells (blast and burst). This works exactly as it did in 2e as well, with a lot of DM fiat.
Finally, you have to worry about whether someone is adjacent. Largely it solves itself by people who engage the same enemy or describe themselves as coming to aid of an ally.
Otherwise it is mostly a matter of "strong attack", "medium attack" and "weak attack". Those are largely when the character wants to spend resources rather than something that is minis dependent.
So it is possible to do, but I would suggest using fewer enemies in play at once than you would use in a normal 4e game with minis. It can be hard to keep straight if you have 10 enemies on the board at once.
Also, I would cut the warlord class. The cleric grants buffs at range, but the warlord generally depends a lot more on the exact position and actions of his allies for the buffs and extra attacks he grants.