Some nights, I think 4e works better without a healer, than with one. Of course, I usually wake up, and can't make up my mind if it was a vision or not.
With that said, I think the (few) games which had no cleric during my last campaign, went fairly well - much better than anticipated.
I don't think this is some fever dream - I've had the same experience. Having a leader seems to increase the grind.
My 4E experience has been with small (2-3 player) groups, so we're always missing a role, and I have to tailor encounters somewhat for the group.
When the group had a leader fights of the appropriate level tend to not be a challenge at all, and are just a very slow attrition of the party's surges.
To provide a single, challenging encounter that has any potential for PC death the fight needs to last long enough to wear down all of the party's healing reserves, which can take long enough that everyone is down to using at-wills.
So far we've seen all of the leader classes in play at the table but the Shaman, with the cleric being the worst offender.
Parties made mostly of strikers and defenders haven't had the same problem with grind. Beyond the improved damage dealing capabilities of strikers, fights with smaller groups of monsters (compared to those needed to challenge a group with plenty of healing) can present the level of danger needed to give some excitement and challenge to the encounter.
Note that this might not be a problem if you only run pre-published modules and don't tailor any encounters. At one point one of my groups caught on that improving their healing capabilities resulted in a Red Queen Effect - "It takes all the running you can do, to keep in the same place."
The most fun (IMHO) you can have while playing DnD is when you come inches away from a TPK but the PCs hang on by the skin of their teeth. Any changes I made to 4E healing would increase the danger level.
All my players remember that time they were one die roll away from being killed by Rhodintor on the roof of Pythoness House while I ran
Night of Dissolution- noone remembers the cultists they slogged through with their at-wills in
The Last Breaths of Ashenport.