I’d recommend trying the Life Line Ocean Kelp supplement. I’ve had my dog on it for the last 3 weeks or so (after reading about it here), and his breath has noticeably improved.
It’s also pretty economical, especially given that a 20 lb dog (the weight my dog is) only needs 1/4 teaspoon a day. I sprinkle it on his kibble (which is also dampened with water), and he eats it right up.