If we don't start the war, then the narrative already exists. For example, Kosovo. Most of the world thought that the Albanians were being ethnically cleansed. When we intervened on their side, we had the support of everyone who agreed with the existing narrative. (The Serbs of course had a different perspective but that wasn't the military's problem: let the military kick their ass and let the State Department worry about patching things up with a defeated enemy seems like a good division of responsibilities to me.)

The North Vietnamese had a narrative before we intervened too: foreigners keep trying to occupy us, but through continuous guerrilla we''ll inevitably be liberated. No matter what we did militarily we couldn't change their narrative.

RE: Al Qaeda. I think the most effective counter narrative is a sound bite. Al Qaeda blows up more Muslims than they do "Zionists and Crusaders." It's true and effective with the target market: potential AQ recruits.