See the Shulchan Arukh OC #567:3
"A person that usually rinses his mouth in the morning should not do so on a public fast, but on a personal fast day, since he spits out, it is allowed .... RAMA: One is allowed to chew cinnamon sticks and other spices to give taste to one's throat and to spit out except on Yom Kippur."
It would seem that, Sephardim have a problem with brushing teeth but not Ashkenazim.
The Mishna Berura #11 states explicitly that if a person is distressed by their lack of teeth brushing / the taste or smell of their mouth, then "in a situation of distress rinsing the mouth is permitted on public fasts, but one should tip the head forward so that it should not reach the throat! This is allowed EVEN on Tisha B'Av but on Yom Kippur one should be stringent."
So the conclusion as it appears to me is that certainly on 17 Tammuz, one may brush teeth with toothpaste. On Tisha Bav, Arukh Hashulchan is machmir. Seems that the MB is lenient.
If you want to know the Islamic Halakha look here and interestingly, they have detailed Halakhot of teeth-brushing. (disclaimer: I have no clue whether this is a Modern Orthodox Islamic Halakha site or a more Haredi one???!)