1 Hex = 7 leagues across ? Makes 1 Hex roughly 30-some leagues^2
Stat Blocks are situationally dependent, not hard and fast. Guidelines, not strictures. Not changing them willy nilly.
Levels are handed out via exploration, not via XP.
Consider having players keep extra characters premade. Like character stables from Dark Sun.
Random encounters. Running is always a viable option, for PCs as well as NPCs. Some creatures may hunt you down though.
Consider giving daily powers and HS’s back to characters via certain accomplishments in a given encounter area. Also, if an extended rest is attempted in an encounter area, a skill challenge for setting up a suitable area may be needed, the complexity of which would be dependent on any number of factors. “Alternatively, there could be some ways that clever PCs could divert a search effort by the dungeon’s inhabitants. Rituals in particular are good for this sort of thing (hell if they’re high level, try Guards and Wards-it’ll be hilarious!) You could even use it as a skill challenge, with the fighters making checks to fortify the rest area and set up crude traps, and the rogue and similar sneaky characters setting up false leads or leading the soldiers on a wild goose chase while the magicky types use rituals to aid the other two.”
Also think on dungeon repopulating tactics.