Where can I eat fish eye in Japan? Ideally, they'd be pickled and come with rice, like I've heard it was during WW2, but I'm not sure whether it's available like that nowadays.
Is it generally available in most parts of Japan, or only in specific areas?
What kind of eatery am I most likely to find this dish?
I'm aware of only one fish eye dish in Japan, namely maguro no medama-ni (マグロの目玉煮), "stewed tuna eyeballs". It's occasionally branded as the more palatable "マグロのDHA煮" after DHA, a fatty acid found in eyeballs and fish oil that's supposedly good for you. Like the name says, this consist of tuna eyeballs (which are pretty big!) stewed for hours on end in the usual Japanese soy-mirin-sake-dashi base until they more or less completely fall apart into mush, as shown in this picture (not CC so I can't copy it in, alas). Incidentally, the pupils and eye sockets stay hard, you only eat the stuff in the middle.
This is not an everyday item by any means and it falls squarely into the category of chinmi ("rare tastes"), meaning odd foods/acquired tastes meant primarily as accompaniment for drinks, and the kind of thing that makes an occasional appearance in the daily specials, not a fixture of the regular menu. A search on restaurant review site Tabelog reveals 15 hits in the entire country, all in reviews where people claim to have eaten this. The only place I could find (and I didn't look all that hard, mind you) that has this on their website menu is a tuna specialist called Hanamaguro (花まぐろ), rather inconveniently located in Kochi city on the southern coast of the island of Shikoku, whose まぐろ漁師の賄いもん 目玉の煮付け ("Tuna-fisher's catering item, eyeball stew") will set you back ¥680. Itadakimasu!
The idea of Japanese dish of pickled fish eyes and rice from WW2 you've heard of is apparently the creative invention by Warner Bros. The image of a canned pickled fish eyes with rice can be found in one of their educational shorts series called Private SNAFU created for the U.S. War Department. The bizzare fictional dish was concocted to make fun of "fishy" Japanese, I believe. Check it up in the episode #17.
The food is very impressive and eye-stunning, and interesting even for Japanese eye. But, sorry, it's not a true dish. Of course, you can enjoy the food "stewed tuna eyeballs" as already mentioned by @jpatokal, at some seafood restaurants (not very common, but not so uncommon) in most areas. 
