I would have said
Sorry I am late. I had never been here.
Because I would, at that moment, be there. Of course, I am not there now, so I do not use the word "here" now. But I would have used "here" in the moment. Now that I am no longer there, I say there. I am always here in the present, but in the past I may have been there. Although I was here in the morning as well.
The "before" at the end would magnify that sense of prior to that moment, but I think that the "had" is sufficient. There is an English grammar "rule" not to end sentences with a preposition, so some would prefer not to end the sentence with "before" to comply. However, non-compliance is common, particularly in spoken English. Adding the "before" to the sentence with "have" makes it descriptively correct if not perfect grammar.
You could also say
Sorry I am late. I had never been here previously.
"Previously" is never a preposition, so it won't make people think that you are ending a sentence with a preposition. But "previously" doesn't come through as naturally as "before" does. It sounds more stilted and formal.
Sorry I'm late. This is my first time here.
This also works.
To restate, here is where I am now. There is someplace that I am not currently. So in your original sentence, it should be "here" rather than "there" because you are currently at the time of speaking at that place.
Now, you might say
Sorry I was late. I had never been there.
Because you are presumably no longer in that place. So it is now there rather than here (wherever you may be now). Unless of course you are reading this on your mobile in the same location. Then you would properly still use here.