I wrote, "He has still never eaten cheese." and it was not accepted, I assume because Duo considers the "still" either redundant or superfluous here.
No, it considers it wrong.
noch nie means "never".
Not "still never".
Similarly, noch nicht means "not yet". It does not mean "still not" (= immer noch nicht).
How would you convey "still never" and "still not" in German then?
"still not" is immer noch nicht, as I wrote above.
"still never" doesn't make sense to me. Can you give me a couple of sentences where that expression would sound natural to you? Especially ones where you couldn't replace it with "still not"?