One of my favorite posts about 4th Edition D&D - so many people were convinced that it could not do certain things that they never tried ...
Early on I wasn't sure how this would work - thought there was certainly no lack of insistence online that it could not work - but after spending a couple of years with the system I don't see it as being any more difficult than earlier versions. Let's look at some of the published material:
The best out-of-one-book option is Neverwinter. I've come around some on this setting from my original take on it. No, there isn't a traditional set of encounters or an adventure in it, but what is there is a pretty solid sandbox. There is a ruined city and the surrounding wilderness, mapped out in some detail though not exhaustively so. There is mechanical support through the themes that tie a character to the local situation. There are factions within and without to give the PC's hooks to look for, sides to take, allies and enemies to deal with. Each one has goals, a history, a list of creatures associated with the faction, a leader with a name and a personality, and typically some monster stats or stats for the leader as well. The whole thing is built for levels 1-10 and there's more going on there then one party could finish before leveling out of that range. Given that and it's small geographic area I think it's perfect for running multiple groups and multiple characters per player in an old-school style campaign.
The most complete published sandbox is the Nentir Vale. First presented in the 4E DMG, that material covered an overview of the vale and its history along with the fairly well detailed town of Fallcrest and a small starter dungeon. Over the next couple of years we saw more detail on specific locations like Shadowfell Keep, Thunderspire mountain, the active dwarven city of Hammerfast, and the ruined Tiefling city of Vor Rukoth which were all published as module-type products. Then we finally got the Nentir Vale Monster Vault which is full of things like a unique red dragon that lives in one of the mountain ranges, a spirit that haunts a certain area in the vale, and monster stats for specific tribes of orcs and barbarians along with notes on where they live and what they are up to. Put it all together and it's a very solid set of resources for a region roughly 200 miles long and 100 miles wide. Players can wander through the vale looking for rumors, contacts, patrons or just plain trouble. Have your players roll up a party, drop them in Fallcrest at level 1 and let them decide what to do next.
If these are too conventional then there is always the Gloomwrought boxed set which pretty much presents a city in the plane of shadow as a sandbox with factions and creatures similar to he Neverwinter presentation but with the weird meter cranked up several notches. I don't own this one so I can't go into as much detail (and it doesn't really push my buttons as a DM) but I think it might serve a somewhat higher level range than the first two - certainly at least 10-15 should work. The shades of gray to just flat-out evil party will probably be more at home here or at least will see less interference from do-gooders. There is also plenty of material on the plane of Shadow in the Heroes of Shadow book and the Manual of the Planes, plus there was a Free RPG Day thing covering another nearby domain. So if you want to go dark, there is a sandbox option for you.
A less-developed option (though there are plenty of resources from other editions out there) would be Sigil from the DMG2. It takes up 26 pages of content in that book including a map, stats for some typical street encounters, and a short starter adventure. It's not a block-by-block description but it's a good overview and certainly enough to start up a DM's imagination. Plus making the City of Doors the hub of your campaign lets the players go just about anywhere they want - demanding on the DM to be sure but it also means the players should never be able to say they're bored with the campaign or tired of the same old scenery.
Another slightly less developed option is the Gray Vale in the Forgotten Realms Campaign Guide. There's the town of Loudwater, notes on the history and geography of the surrounding area, a starter dungeon and some smaller encounter areas, and some of these other areas are developed in Dungeon magazine. It's mainly lower Heroic Tier but given the are of the Realms that it's in that can certainly be amped up without much trouble.
The main thing all of these published areas share is no metaplot. There is no overarching story driving things forward. There is a base area, various factions going about their agendas, old legends about people or places or things, and lairs and dungeons and wilderness to be explored. That's exactly the kind of thing you need to run a sandbox regardless of edition. Keep something like Dungeon Delve handy in case the players head off in a direction you were not expecting, or a PDF collection of dungeon and access to a searchable index and you should be good to go. DDI and a printer or the ability to rapidly cut and paste monster statblocks into one document could really help with on the fly encounter generation as well.
How would I run it given 4E's heavy emphasis on balance and XP budgets and set piece encounters? Originally I was thinking that zoning a region for different levels, like an MMORPG, would be a good approach but I don't think you need to do that. Rather than geographic level distribution I would look at faction-based level distribution. For example, we know the Bloodspear Orcs have member creatures that cover certain levels, maybe from 4th to 8th. Say we also know they live in the Cairngorn Peaks. I would work up three patrol-type encounters that include what I think their typical patrols would consist of and start with those. Maybe one is a light recon patrol of speedy skirmisher types, another might be warg-riders, and another might be a heavier one with a shaman and a couple of ogres and orc berserkers. The main idea here is that I don't let a set "regional level" drive my choices - instead, my choices determine what level it ends up at. If I end up with a heavy orc patrol that turns out to be level 9 when I add up the XP's well that's the way it is - hope the party is up for it or that the players are smart enough to run if not. If I'm doing random chance for wandering encounters then in the Cairngorns I would pick one of these when the time came. If I do a full-blown random encounter chart then I would make sure the known home territory of the Bloodspears had a pretty good chance or orcs for random encounters.
Now some might say "but what if they level past the region?" - let them! You don't have a metaplot, remember? You could decide up front and say I will run this area at Heroic for one calendar year as-is. Maybe players will try multiple characters. After a year you can change things up - maybe the drow burrow up from below, maybe someone opens a gate to the Abyss, maybe the Gityanki start showing up en masse for some reason. Conversely you could have the entire area annexed by some kingdom and become too peaceful for adventuring and it's time to move on to a new area - maybe Sigil. Whatever it is you can have something drastic happen to your sandbox either upping the threat level into Paragon or wrapping it up and changing to a different campaign - or, enforce character retirement. When a PC hits 11th level they get one last adventure and then have to retire to something respectable like high priest or local baron or they take a trip to Gloomwrought or something. You could also move things downward and have more powerful heroes recruited to stop an underground threat like the drow and work up a whole Underdark sandbox in the same region and have a war going on deep beneath the surface with duergar and deep gnomes and drow and all of that lore. Not every group is going to want to go there, but it could be a cool option if you intend to have both tiers in play at the same time.
Anyway I mainly wrote this up to show that not only is sandbox play possible, but based on the amount of material published for it I would say it's even been encouraged by WOTC. The ease of up and down leveling monsters in 4E makes adjustment quite a bit simpler than in previous editions and if you're willing to run wit ha computer at the table tools like DDI and the numerous PDF products out there make seat-of-the-pants Dm-ing even easier. I do not typically run with a computer at the table because my players tend to stay focused on a particular goal or rumor or mission rather than meandering about like so many of us did in the old days, but it doesn't mean that I couldn't - it's mainly because I haven't needed to do that. Maybe next campaign.