I'm probably missing something rather simple but a cursory check has not given me a suitable answer -- when someone bakes challah and takes that chunk out to be put aside for a kohen, because the local kohens are all tamei, the challah must be burned. I know that there are different traditions and halachot about how much it has to be burned, covered or not etc, but my concern is that afterwards, the challah is either thrown out or buried. Isn't this going against bal tashchit?
"Bal tashchis" is a prohibition on destroying something for which there is potential use. Destroying something that has no use is not in violation of that prohibition. Because there is no use for separated chala (because, as you note, there's no one around these days who can eat it), one may destroy it. Moreover, one can separate the chala even though it will wind up destroyed, because fulfillment of a mitzva is a valid reason for destroying something: it does not violate "bal tashchis".
Source: This is common knowledge of the prohibition of "bal tashchis". One example source is the Chinuch (529), who writes (in my own loose translation) "...but certainly it's permissible to cut them [=fruit trees] if he finds a purpose in doing so... and any non-fruit tree, [the rabbis] said, one may cut even if he doesn't need it...". As an example of the permissibility of destroying something for a purpose, Mishna B'rura 560:9 writes that it's permissible to break a cup at a wedding "since they do so as a hint to a lesson, so people place it in their hearts".
Doing something the Torah tells one to do can never be a violation of the Torah.
Destroying chometz which one finds on pesach isn't baal tashchis either, since if the Torah says you can't use it or have benefit from it then by definition the prohibition of baal tashchis is removed.