US Postdoc in Japan not allowed to be first-author due to being foreign. How to proceed?
While what you are describing is entirely inappropriate from a perspective of scientific ethics, I would not be surprised if:


there may be a language/culture miscommunication causing you to misinterpret the situation, or
there is indeed an informal policy of this sort amongst some laboratories (but individual labs all over the world sometimes have odious policies)


Anecdotally, while I have not worked in Japanese academia myself, I have Japanese colleagues who don't appear to have such a policy and have non-Japanese colleagues who did postdocs in Japan and published as a first author.  Such a policy is at least thus not extremely common.

So, what should you do?  


First, I would recommend starting from the position that this is a mis-communication and asking how your advisor recommends you getting first author publications during your postdoc, since this is important for your career.  
Your advisor is unlikely to say no (for a number of reasons), but if they do not give you a clear path to getting first-author publications, then I would indeed suggest finding other people to work with, while doing what's necessary to maintain relations and face with your current laboratory.
Finally, note that while first author publications are wonderful, "co-first-author" and second author publications are also good, and if the common denominator amongst a number of papers is you, then people will likely recognize that fact.