Personally I would not even consider the native language school. Partly because it won't offer challenge, but you have the added handicap of the English speaking kids holding the level of the class back, and the opportunity to learn English (or any language) as a native speaker is invaluable. That leaves the expensive English school or the gifted English school.
Assuming you can pay the expensive fees, how about gong there next year and the gifted school the next year or later on? He'll have the challenge of learning English next year, but once he's fluent you could move him.
Instead of a tutor, are there weekend or afterschool schools in the other languages he could attend? I don't know where you live, but they exist in lots of places, expressly for kids like yours - children if immigrants who want to make sure their child learns good grammar, penmanship, culture in their native language.
