Japan ’s immigration laws require you to have a bachelor’s degree (in any subject) to be eligible for a work visa. If you have a degree and your native language is English everything is pretty much straightforward once you have found a company to sponsor you. If you are recruited in your home country, your new company will provide the paperwork so you can get a Certificate Of Eligibility (CEO). This can take up to 8 weeks to process. Once you have a CEO you can get your work visa, which usually takes a week.
We have a native french speaker here, but he's from quebec. His English isn't native, as he attended school in French, and even has an identifiable accent to native speakers- BUT, and this is a huge but, Canada is an English speaking country. He got in through the system because no one bothered to ask him if English was his native language, per se. They just assumed.