I am DMing a new 4e group, and I am interested in approaching the game as a "theater of the mind" style combat rather than the traditional grid format.
So. A few thoughts. Like a lot of the other answers, comments, yes, 4E without the grid is stripping a major feature of the game out.
The other major question that comes up is "new group" - new to 4E? New socially - have you guys played together before, have you run for them before? Or like, simply a new campaign? Have you already spoken with them about your idea of removing a major part of what makes 4E, 4E?
If I were playing with people fluent in the 4E system, who I've played with before, and this is what the group wanted, then we could actually even consider this. If they're not fluent in the system, it's going to be a lot of work on their part having to learn 4E, then try to learn what powers will actually be useful in a non-grid game. If we're not all familiar with each other as a play group, stripping out major rules seems like a huge jump on top of getting to know each other.
Let's assume you actually have cleared ALL of those hurdles. Ok. Here's what happens next:
Design each encounter with environment bits
A great number of the powers work in positioning opponents, positioning yourself, etc. to set up either flanking positions or to force opponent's into damaging/dangerous areas. This means you're going to want to have a variety of objects/things which can be thrown, knocked over, would hurt to get pushed into (pushed off of, etc.).
Be aware that a "Square" = 5 feet. So if you put things too far apart, people cannot use them.
Go to page 42 in the DMG. Write down some of the damage and condition effects some of these things have.
For myself? I'd have to draw a simple sketch to keep track of where everything is at least.
Declare positions, every turn, every round
Now, for players to make useful, meaningful choices using the powers they have, they will need to have enough information about where everything is. How far away things are, the monsters, etc.
You will have to declare this, to each player, at the beginning of each of their turns.
"Oh, well, I should just explain it once and they should remember." Nope! The fun of D&D is danger and adventure, not playing Memory. If you expect them to hold it in their heads while the turns go around the table, you will quickly find three things:
They will forget and either start making bad decisions based on incorrect information/assumptions
They will end up asking you the above information, over and over, so you might as well declare it each round anyway.
They will default to the most simplest powers/least strategic choices because that's the only thing they can remember will work.
Does this seem like a lot of work? Yes, it is. Removing the grid either means you take the role of the grid, and have to explain things over and over, or you ignore 60-70% of the powers and meaningful choices built into 4E.
Literally at every point, the question becomes, "Why play 4E D&D instead of something else?"
Options
Find out what your group wants. If your group really wants gridless play, I suggest using a game that works better without a grid. If they really want 4E, odds are pretty damn good they also want to play with a grid.
Other, free options: