You can avoid a formal name, but in doing so, you're making a statement, and any addressing of the character may simply turn it into their name.
Using a first person perspective for the main, non-invisible character is certainly doable. The narrator of Fight Club remains unnamed throughout the story, and has dialogue with various people. Perhaps the author's minimalist style should be considered though, as it likely helped remove the characters' need to address people by their names. The dialogue is punchy (heh) and sparing.
That leads into this thought though: names in real life almost always have meaning, and many names are chosen with intention. Look at the bible; every name has an actual meaning in the ancient Hebrew, Aramaic, and Greek languages, and many of them give some foreshadowing to the character's role. Adam's name literally means "the man" or "the human", and has similar roots to the word "earth", of which he was made.
Back to Fight Club, one could argue that the narrator's namelessness not only helps veil the twist, but also speaks to the character himself, without explicitly using words. Fans and critics assign him a name or call him "the narrator", and the sequel does give him a name, but these were born out of convenience and legal necessity, respectively.
Maybe this helps you think about "the girl" or "the maiden" or whatever you want to call your main character, since, even if her Name isn't determined by the town leader, your readers are going to call her something, which in turn will have its own power behind it in speaking about the character.