I'm now running a DK and 4 ele shamans, level 78. Obviously haven't done any heroics yet but all regular instances have been absolute cake, and I can't see myself wanting a resto shaman at all once I do heroics. In fact I can say I definitely will NOT spec one resto. If 5 elemental shamans can handle heroics, a DK and 4 elemental shamans sure as hell can. DK will do as much or more damage than the elemental shamans anyway so the "burn things fast" tactic still works. You shouldn't need a dedicated healer which will only add complexity to the setup and reduce your DPS.

Keep in mind with DK + 4 ele shamans you still have 4 earth eles and/or 4 fire elementals for extra tank/DPS as needed.