A friend of mine whose player group really wants to try 4e asked me if I had seen any rules or even ideas for playing 4e without minis and without grids. He's willing to run some 4e for his players provided that he doesn't have to use minis and battlemats. After a couple of hours hunting around on the web, I was able to find a lot of people arguing that it could not be done without completely nerfing the game for those character classes whose powers depend on exact positioning and moving other characters/monsters around. However, I did find a handful of forum threads and one wiki discussing how to play 4e with narrative style combat instead of skirmish minis style combat.
Just in case there are others interested, I'm listing the links I found. I can't comment on the ideas presented in them, however, as 4e just isn't my thing.
Message Board Threads:
4e rules will make some games much harder to run (Post 25 is by Mike Mearls saying it is possible to run 4e without minis.)
Scared about squares
Boardless combat rules
Help me! I don't like 5-foot grids!...
No Miniatures, Gridless System
Sally 4th: The Basics