Grease his boots or axe handle?

Spam the heck out of Daze?
Run/hide until Rage wears off and he's fatigued?
Trick him into charging a silent image?
Sleep spell?
Get him into a narrow choke point and have the sword & board Fighter stand in his way Fighting Defensively w/ Tower Shield?
Judicious use of readied actions...
Really, the one theme of nearly any advice for how a party deals with such a foe is anything that prevents him from ever landing a single hit. Because it will very likely kill someone.
I'd just avoid using the amped up damage barbarians until the PCs have more hp. First levels is dangerous enough already, and putting in enemies designed to deal a maximum amount of damage on a hit isn't going to be fun, unless you want a very gritty, deadly game. This isn't really a flaw in the system, barbarians at first level
should be incredibly deadly. Just because it's CR 1 doesn't mean you have to use it. Such a foe would actually be pretty great to have a group of when the PCs are level 3-4, weak enough in defense/hp to be felled easily, yet still with the attack and damage numbers to make the party sweat.
And if you do have a party with the spells/tactics to keep him from getting a hit in, it could actually be a pretty great encounter. It'd be like the first episode of RoLW (the TV series), when Parn (Fighter) is taking on Orson (Berserker/Barbarian). Orson keeps missing, but the attacks are so blatantly powerful and deadly Parn's gotta be afraid of what happens if Orson were to get lucky... Definitely give such an NPC Intimidate ranks, and maybe a flaw so he can have both Power Attack AND Intimidating Strike -- double the attack penalty, twice the fear-mongering!