This may seem like a trivial distinction, but as a title choice it's important as the title conveys an overall sense of the tone of the story.
First of all, the use of the contraction didn't is less formal than without so it might be best to consider the verbiage you've used throughout the story and match the word choice to the formality of the voice in the story. Next, "without" is more concise as it's a single word, and can't is a contraction of two words plus requires the use of "have". If your language is meandering in the story and not overall concise, to show your reader that you would maybe consider can't.
Now that the technical differences are spelled out, without conveys an absence of a soul, when I hear "without a soul" I think of a void, of absence and of longing, and seems more wistful of the two, whereas "didn't have" seems less of a statement of absence and void and more a statement of loss. None of that is specifically spelled out by the definitions, this is more of a connotative distinction and more of a conveyance of the unspoken feelings the words conjure. If the story is more about loss, maybe "didn't have" is better, whereas if the story is about absence, a void and of longing, it seems that "without" would be a better choice. Didn't have also seems like it has more of a 'concrete' or definite feeling, as opposed to the wistful ethereal feeling conveyed by without. Again, pick the choice that is more in line with the words you've used in the story.
Finally, and maybe the most important consideration, "didn't have" is past tense while "without" is present. If the girl gets a soul later in the story, it may be more apropos to use "didn't have", or another synonymous past tense phrase, if she doesn't get a soul, it might be a better idea to use "without". That said, if your style is to withhold clues from the reader about the ultimate end of the story rather than try to let them guess at your intention, reverse that advice.
Hope this helps!