No, you can't run D&D 4E without a battlemap.
Playing 4E without any kind of map at all using only narrative techniques requires you to ignore half the powers on the character sheet. At that point, you might as well play a different version of D&D.
I know that people are saying that they have actually done it, and this should be enough to prove that it's possible. However, I think that to pull this off, you have to add so many house rules and ignore so many existing rules that it's questionable whether what you're playing is "D&D 4E" anymore.
Let's tackle some of the reasons:
Define "Battlemap"
First, I'd argue that, once you draw a zone diagram or start tracking range bands with miniatures or tokens or even words on a piece of paper, you just created a battlemap, albeit a much simplified one. Playing 4E with no map at all means tracking everything important in your heads.
The rest of these reasons concede that a zone map or a range band diagram probably aren't what the original question means by a "battlemap."
Position
Without a battlemap, there's no way to accurately track position. A lot of games handle position differently, with zones or range bands, and that's awesome. 4E does a lot more with position that that. There are rules for flanking, areas of effect, line of sight, cover, difficult terrain, and so on -- and these become mere shadows of themselves without a battlemap.
Movement Effects
Sure, a range band system lets players push, pull, and slide targets around and track where they end up. Because of the positioning problem, discussed above, however, the main reasons you'd want to push, pull, or slide go away. How do you slide your ally into flanking position?
Areas of Effect
Those powers that target a blast or burst now need a new system for determining who can be targeted. How many times in 4E have you held off with some area attack because your fighter was up in the middle of it? That won't happen without the battlemap.
Terrain
Terrain makes combat exciting. Having to scale a wall to get at the archers, or avoiding the edge of the lava pit while fighting the ogres that keep pushing you--that's the excitement of D&D combat. While there are likely creative zone solutions for these things, they're often more complex than just using a battlemap.
Tactical Play
At its heart, 4E combat is a tactical game. The reward system -- leveling up -- is about choosing new tactical powers for your character to make them more effective in combat. Remove those tactical options, and it's not 4E anymore. Why not use a different ruleset that doesn't require a battlemap?
I have yet to find/figure out a simple way to deal with move effects that satisfies optimizers.
– Aug 27 '10 at 08:24