I did the mage tower quest early on, and ended up unwittingly killing Wynne. My player is a warrior. This essentially means that when I go to fight Flemeth, my only party choices are warrior and rogue characters (since Morrigan can't come on that quest). I've tried several times in easy mode at different levels, and get stomped rather quickly every time (it seems like Flemeth levels up as I level up). Are there any tactics or tricks to this fight that can be pulled off without magic?
Yes - a ranged party can take Flemeth without any mages, but it will require high fire resistance. See this wiki article on strategies to defeat Flemeth. I recommend getting Wades Superior Dragonbone Plate for whoever is tanking (very high fire resistance) and using other fire resistance boosting gear for the remainder of the party. Use Greater Warmth Balms for additional temporary boosts.
You could also try the ranged strategy demonstrated in this Youtube video (uses Shale, Zevran, Leliana, and the main character is a rogue). Supposedly this was done on Nightmare difficulty.