Cross contamination is not an issue for my wheat allergy, so i'm luckier than most and can usually navigate through a menu on my own.
I always have great luck with japanese, but bring my own tamari soy sauce as i find many restaurants serve soy sauce with wheat. I eat mainly the sashimi, sushi rolls with fish only, no tempura, rice, miso soup, sunomono salad, and avoid the sauces.
I would talk to the chef and see what he or she can do for you - i'm sure you'll have a wonderful meal there.