I titled a short story "The Girl without a Soul". But recently I've been thinking on naming it "The Girl who didn't have a Soul."
Do they mean exactly the same? Which sounds better as a name for a short story?
Questions on English Language & Usage Stack Exchange are expected to relate to English language and usage within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.
Yes, they mean exactly the same. There are plenty of stories that have "who didn't have" in the title; and it really doesn't connote an event in the past. By contrast, Amazon has no fiction books with "who doesn't have" in the title.
It's very common to use the past tense in the title of a story, without any implication that something happened in the past, or that something is not happening in the present.
To answer the second question, "The Girl without a Soul" flows better in my opinion.
To your second question first, because it's easier, "The Girl Without a Soul" would definitely sound better as a title of a story.
These two phrases do not mean the same.
"The Girl who didn't have a Soul" sounds like a story about a Girl who once did not have a soul, but may have one now. This phrase emphasises the fact that the Girl had no soul in the past.
"The Girl Without a Soul" sounds like a story concerning a girl without a soul, and implies that this is the case throughout the whole story. It does not give the impression that the Girl will, at the end of the story, have a soul.
However, the difference between these two statements are so slight, to dwell in them would be pedantic. Based on how your story goes, you could choose either statement. However, "The Girl without a Soul" does sound better.