Suppose that Mary is eating sushi now. Which of the following sentences should Mary use?
(1) "I have never eaten sushi before."
(2) "I had never eaten sushi before."
Suppose that Mary is eating sushi now. Which of the following sentences should Mary use?
(1) "I have never eaten sushi before."
(2) "I had never eaten sushi before."
So, this is a case of present perfect (I have) versus past perfect (I had).
In this case, since the sushi eating is in the present, it would be "I have". If you were telling a story about the first time you ate sushi, you would say 'I had', i.e. 'I had never had sushi before, but I loved it.'
Note that in English, you can also use 'to have' in this case. So, 'I've never had sushi before'.
You can make a case for both present and past, but neither seems a particularly natural or normal thing to say in that context. Try something like "This is my first time eating sushi." instead.
It might make more sense to consider the question to ask Mary: "Have/had you ever eaten sushi?" If she is currently eating sushi then "Have you" would be an odd question (since the answer is obviously "Yes"), so "Had you ..." would be better.