My understanding is that fast food ingredients are adjusted to match the palettes of the locals, but I would expect that Vegemite would still be off the menu at McDonalds. True?
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.