You're absolutely correct that every native speaker of English would understand "I haven’t never eaten sushi" to be exactly synonymous with "I have never eaten sushi" -- no one would be confused by the double-negative and think it means "I have eaten sushi". So, the teacher is applying a rather artificial standard, as though human language were a mathematical formula.
On the other hand, I would say that double negatives belong to the category of English "просторечие" -- it sounds uneducated if one uses double negatives habitually. However, well-educated speakers will quite often use double negatives for rhetorical/artistic/humorous effect. (For example, the song "There Ain't Nothin' Like a Dame" from the 1949 musical South Pacific.)
So, non-native speakers should use double-negative constructions with caution -- otherwise people will think that you don't know the basic rules of English grammar.
P.S. Never use double negatives is one of those Grammar Rules that are taught to younger children in school, along with Never split an infinitive and Never end a sentence with a preposition. (In fact, some of the greatest writers in the English language have broken all of these so-called "rules".)