Some US Air bases have aero clubs, and they are all looking for CFIs. There is Yokota AFB and Kadena AFB in Japan. I'm actually planning on getting my CFI and start working at Yokota this summer. They won't sponsor your residence status in Japan though.