1...If "I have never done it before." is simply a statement of fact, why do you need "before". Just say 'I have never done it.'
2...I think that "I never did it before." sounds odd to you because UK English speakers are fond of using perfect tense in situations in which North American speakers often use simple past. 'before what?' is the same as in the perfect tense sentence, 'before now'.
3...Your last sentence, the past perfect one, of course needs the specified time reference "before I went to Australia." But in the present perfect 'I have never...', the time reference is is now, so why would one need to add "before" unless there is some contemplation of the situation changing.
I'm in agreement with you!
1. The 'before' in "I have never done it before" is unnecessary because the present perfect contains that implication....I only included it as it was in pikipiki's original sentence. It becomes more relevant in a sentence such as "I've never tried this before," as you are about to eat your first mouthful of fricasseed toad!
2. Yes, UK English does not use the simple past in this way....although it's doubtless seeping into it via US films etc.