I really don't see how you need more then 2 healers for any fight in 10 man naxx. Although a dps who can heal would be beneficial. since we did 10 naxx in 2 nights ill break it down by fights that might be hard.
Patch one healer on MT one on hateful is all that is needed from my experience. Believe we had a pally for mt and myself, disc priest for hateful. Took a couple attempts, healing wasnt an issue, bad dps was. (namely 2 people who were between both tanks in damage. I hate bringing along people doing 1200 dps.)
We found grob to be hard, however I have heard people saying he is harder in 10 man then in 25 since you have a higher % of your raid running off with the poison at any one time. Eitherway once we ditched the 1.2k dps people for 2k dps people we one shotted him. If your dps has been at 80 for more then a week they should be able to break or be very close to 2k dps. Otherwise send them here to learn.
Gluth was easy, one shotted with a DK solo kiting.
Thaddius easy, two shotted. First attempt we explained the adds then thaddius, by the time the adds were dead the new people in the raid had forgotten what we said about the charges.
Spider wing all easy mode, wiped on faerlina once since we didnt know about the changes, being immune to MC sorta makes the fight different. Tank could only tank through enrage until 30% between pain supression, trinkets, and a little luck.
Plague wing all easy mode, DDR took a couple attempts but nothing that was due to only having 2 healers.
Loatheb was close with only a pally healer and priest healer. But I designated 3 people for the pally to heal in G2, and I timed a PoH to land shortly after debuff wore off for G1, followed by a pennance and flash for the two the pally couldnt hit. Priorited shielding the guy hit by flash since he always recieved the least heal. He was also a dk so he took the least amount of damage.
Instructor took us two attempts since the fight is a little different in 10 man then what we are used to. Pally/Disc priest still had no issues healing this. Each of us was assigned one add to heal. I also healed through the raid damage. Gothik we accidently aggroed and still one shot. Groups were set up, however buffs werent out and we were explaining the fight.
4H, kel, and sapph was all in night 2. We lost the pally healer, group set up was as such. 2x disc priest, shadow priest, moonkin, DK, 2 prot warriors, rogue, ret pally, hunter. This is where i say offspecs that can heal can help alot, although I dont mean they need to switch over and heal. We had the moonkin and shadow priest tanking the two ranged adds and switching every 3 marks, or as soon as their previous mark expired, whichever happened second. The two melee ranks switched every 4 marks I believe, however they waited for a meteor to land so that it wouldnt land mid transition. We had an issue with dps getting a mark refreshed due to standing in the wrong spots, so we needed them to not be part of the tank switch.
The groups were split up as such, if your facing the room, boomkin started in the back right, Spriest in the back left, one Disc priest in the middle on the left and right. Each tank had themselves and 2 dps with them in order for the meteor damage to be spread out when that tank was tanking the meteor mob. The shadow priest did have VE and imp VE. His healing was fairly significant, allowing the first and second marks to not need to be healed for the most part. Each disc priest also found time to dps the meteor boss a little when he was on our side, the healing was very easy.
After the fourth transition both melee mobs died and the fight becomes a joke. The only time someone came close to dieing was when the ranged tanks switch, at this point both priests would shield their ranged tanks to assist them in surviving until they became in range of the other priest.
Sapph, here, on our 4th or 5th attempt we lost the ret pally (1287 dps...) and picked up an enhance shammy. On one of the first couple attempts the other disc priest respecced holy to CoH the raid as I picked up on the MT and assited with the raid. We found this to be pointless. Most of my raid heals were sniped with CoH and the holy priest went oom fast. So she stayed holy to save time but what worked for us was this.
G1 MT, rogue, DK, Prot warrior trying to dps, me.
G2 Hunter, enhance shammy, Boomkin, Spriest, Holy priest.
We both stayed on the south side of the map, on sapphs left side. We both took care of our group with PoH's. We both watched the MT as well. The holy priest kept PoM up as much as she could and flashed a couple times, while I kept weakened soul on him and used penance. The enhance shammy would keep maelstrom weapon procs for a HW on the MT should he ever see him drop below 60%. I think he ended up doing so about 6 times throughout the fight.
We did it with no frost resistance though the shammys totem helped alot. The fight was relatively easy, i feel we could do it again this week and next, while patch might be a little more iffy.
Kel' is a joke in 10 man. Anyone know if the skeleton adds are bugged? They have 12k when walking around then 1.2k when they head for the group. Might be 16k / 1.6k. Either way I one shot them with SW

, or the hunter just fires an auto... the entire phase 1 could be healed by one feral druid in feral gear.
Phase 2 Has only one real concern, and that is the ice tomb effect. We found it to be easy once I stayed within 30 yards of the melee so I would PoH and heal all of them, and the other priest would flash up the MT. Although holy would be better for PoH I feel, I had more haste so it allowed me more room to delay before I had to start the cast. CoH also failed here due to pets, either our BM hunter would lose a bit of damage, or we would have to rely on the priests actually trying. Though I am sure that if your aoe healers were slow you could just have a priest spamming CoH once it landed and make sure no more then 5 targets are in melee range, even if it cuts dps there is no enrage timer.
Phase 3 the prot warrior OT died to the 2 adds, though his gear was really subpar with alot of 70 gear still, the MT was able to tank both adds and kel for the remainder of the fight, just be sure to save PS / SW for when a healer gets tombed.
Overall the entire instance is more/less easily 2 healered. Or, more specifically, 2 healing priests regardless of spec. Not sure how hard/easy it would be with a shaman/druid/paladin to replace one of the priests. What wiped us usually was lack of dps, the Spriest, DK, and hunter all had about 2k-2.2k dps, while the prot warrior had about 800? when he wasnt tanking. Other dps in the group also failed at the meters although i dont attribute that to the class. What kind of dps can a prot warrior pull when not tanking? My biggest gripe is the number of fights where you need two tanks at least, yet besides feral and maybe dk, paladins and warriors dont put out good damage when not tanking as tank spec.