I was in an Eberron campaign with no mage or heavy fighter at 8th-level. We got wasted by a hydra. An ordinary CR-appropriate hydra.
A heavy fighter could have at least occupied it while a wizard could cast Glitterdust, Fear or some other such spell and probably end the fight immediately. (We were on a ship, and could outdistance a blind hydra easily.) Plus, our rogue would do nasty things to it with a ranged weapon from like 20 feet away for the next eight rounds.
There was a higher level campaign I ran where, instead of a cleric, we only had a psionic healer. Not a substitute. The inability to heal at range directly lead to the death of the barbarian character. The lack of "status ailment" spells was only a problem twice, when the PCs were hit by negative levels from fleshbound vampires wielding nasty swords and also Con damage from wraiths. Finally we ended up with a cleric, but he insisted on taking rogue levels and some weird PrC and being evil - I made him take a feat that still let him spontaneously convert spells to healing. The cleric player was inexperienced too - he was very surprised the first time I broke his concentration with a direct damage spell, for instance.
For some reason, groups I'm in, both as a player and GM, almost never seem to have a heavy fighter.
Without the core four, your party is weaker. However, party strength relies on teamwork, tactics and optimization and not just class composition. An experienced party (meaning players, not necessarily PCs) can quickly learn to partially fill in the gap.