I have been living in Japan for nearly two years, about 5 months as a vegan and the rest of the time as a vegetarian with limited eggs and dairy. If you're going to be in big cities, it'll be easier. More people speak English, and there are more veggie restaurants and such. Where I live, I have to explain completely wherever I go: No meat, no chicken, no pork, no fish, no fish broth, no fish flakes, no fish cakes, no shrimp, no octopus, no egg, no milk, no cheese, no gelatin. And then they ask, "how about rice? tea? meat that's chopped up small?"
If you need, I can write all that up in Japanese for you and you can print it out and carry it with you.
The grammar might not be perfect (I'm not fluent) but they'll get it.
Nearly all soups will be cooked with fish broth if they're Japanese style, and meat broth if they're western soups. Even in, say, Italian restaurants, you need to check for things like fish flakes on spaghetti, cheese put into sauce even though it's not listed on the menu, octopus in salads, etc. If you go to a noodle place, cold noodles are usually safe on the broth front, but the dipping sauce will likely have fish in it, so you need to specify soy sauce only. You also need to assure that they don't cover it in fish flakes. Hot noodles will be served in fish broth or pork broth, unless you can find a place willing to leave it in the plain cooking water and add soy sauce or something to make a broth (I've only found one place near me willing to do so).