Your players probably won't like paladins, but everything we've seen indicates that fighters will be damage-dealing powerhouses if you want them to be, equalling or even exceeding striker classes. Look at those DDXP pregen characters. The fighter does 3.5 less damage than the ranger using basic attacks. If she cleaves, it's only .5 less total damage. And that's a fighter built for defense, with a shield. Give her a two-handed weapon and she'd do even more.
The justiciar paragon path may be meatshieldy, but it's a paladin path. Look at the kensei path for fighters. Bonus to damage, bonus to attack rolls, and rerolling missed attacks. Seems pretty offense-oriented to me.