In the McDonald's breakfast menu, Vegemite is available for spreading across an english muffin or slice of toast. And in some of the more conventional hamburgers (not the classic, well-known ones), sliced beetroot is added to the filling.
I don't know about the other outlets. I've yet to find a non-chain sandwich shop that doesn't have Vegemite, but I've never asked at Subway.
Wade.