I'm a lacto-ovo-pescatarian who eats fish but not other seafood, who is living in Japan. The most bewildering thing about your question for the Japanese server is that most Japanese do not consider seafood to be meat. The other confusing part is that they don't generally think in terms of a dish being vegetarian or not (the majority of vegetable dishes in Japanese restaurants also include pork, or beef, or seafood and it doesn't occur to them to make the dish which primarily features veggies without sprinkling one of those in). This is why asking "bejitarian" was met with blank looks even though it is a Japanese word.
Since the thought that you don't eat meat is so foreign to the server and he/she is rather likely to get confused, start with the main point:
First, clearly enunciate as you say, "I don't eat meat":
「肉、食べない」(niku [brief pause], tabenai).
Next, say, while pointing at the menu item, "Does this contain meat?":
「肉は入ってますか?」 (niku wa haittemasu ka?)
Third, if it looks like the person caught on, you can say, "Fish and seafood are okay":
「魚、海鮮物、大丈夫」(sakana [brief pause], kaisenmono mo daijoubu).
Or, if you eat fish but don't eat other seafood, say:
「魚は大丈夫。他の海鮮物、食べない」(sakana wa daijoubu. hoka no kaisenmono, tabenai).
(The server is already likely to have assumed that you can eat fish and all types of seafood even if you don't eat "meat," so you may not find much benefit to saying this.)
One thing to be conscious of regarding sushi/sashimi is that sea mammals, such as whale and dolphin, may be overlooked as being meat, so if you say that you eat seafood, the server is likely to group these within that category, so just take note to avoid those particular dishes: whale = 「鯨」 or 「くじら」, dolphin = 「海豚」 or 「イルカ」
If the answer is that yes, the menu item you're inquiring about contains meat, and so does the next one you ask about, and so does the next one you ask about, then say, while twirling your finger over the entire menu, "Which item does not contain meat?"
「どれが、肉入ってない？」(dore ga, niku haittenai?)
Another option is to order something and ask, "please hold the meat":
「肉ぬき、お願いします」 (niku nuki, onegaishimasu)
This is what I usually do, since I am not strict, but sometimes, though the server agrees that the dish can be prepared without meat, it arrives at the table with the meat in it. This is why my Jewish friend was not able to order salad in any restaurant: she gave up on asking because often it would come with bacon bits or ham slices anyway.
Since you're new to the language, I wrote these in as simple Japanese as possible. Even so, you may want to print them out and carry a small piece of paper with you so you can show the server the printed sentences (or if you will be carrying a smartphone or tablet, to pull it up on the screen). I don't say this because I doubt your ability to pronounce the words, but even if you pronounce them perfectly, you might be met with a blank stare due to a mental block on the part of the server.
Allowed as it is more about the subtleties and cultural differences than the actual translation. -- "How do I say this in Japanese?"