外国人の方に喜んでもらえるような、ちょっと変わったお店がないでしょうか？？ 予算は一人5000〜7000円くらいです。

忍者が出てくるとことかってことぺこか！
場所は四ツ谷あたりぺこ？

志ら井 （しらい） - 四ツ谷/割烹・小料理 [食べログ]
http://s.tabelog.com/tokyo/A1309/A130902/13051510/

四ツ谷駅のあたりで大丈夫ですか？
ここのお店和食がおいしいですよ！
お寿司や和を感じられるお料理たくさんなので喜んでもらえるかもですー

赤丸ヂンギス - ぐるなび
http://r.gnavi.co.jp/a298700/

変わった料理…
ジンギスカンはどうでしょうか？
どこの国の方なのでしょう

KAWAII MONSTER CAFE HARAJUKU （カワイイ モンスター カフェ） - 明治神宮前/カフェ [食べログ]
http://s.tabelog.com/tokyo/A1306/A130601/13184779/#rst-data-head

明治神宮前駅になってしまうのですが、こちらがおすすめです！きゃりーぱみゅぱみゅさんをプロデュースした方が作ったレストランです。きゃりーぱみゅぱみゅさんの世界観のようなお店で、観光におすすめです！

坊主バー(四谷三丁目/バー) - Retty
http://retty.me/area/PRE13/ARE6/SUB603/100000008736/

お坊さんが接客してくれるバーです。いかがでしょうか？

神楽坂 割烹 加賀 個室と会席接待の宴会処 （カッポウ カガ） - 飯田橋/割烹・小料理 [食べログ]
http://s.tabelog.com/tokyo/A1309/A130905/13048623/

日本らしい割烹料理はいかがでしょうか？

京町恋しぐれ 新宿 本館 （きょうまちこいしぐれ） - 新宿/居酒屋 [食べログ]
http://s.tabelog.com/tokyo/A1304/A130401/13000842/

場所が異なり申し訳ないのですが、京都の街並みが表現されていて、舞妓さんもいたりする店です。
外国の方にも人気ですのでいかがでしょうか。