I've only been to Nepal, so I am not sure how much help my experience is....
But anyway, in Nepal there was an abundance of yummy vegie food and most of it was vegan too. The language barrier wasn't a big deal either because almost everyone spoke English. English is compulsory in Nepal and they take learning the language seriously (or as seriously as they can with lack of funding etc) and so most people in tourist spots speak it quite well, as do the children. My friend traveled to Vietnam and Thailand and she said it was the same there too.
I would say for South and South-East Asian countries vegan food wouldn't be too hard to come by.
And I'm told in western places like the UK and America they have so much more amazing vegan food than we do!
When you do eventually go, keep us updated and have heaps of fun
I want to do a big trip traveling soon too. I just need to save the money haha