The first three variations could be said and are natural. The last one is natural but normally without the emphasis on the last words (see below). How they are said orally – that is, which words a speaker stresses – will produce subtle differences in meaning.
John said to me her story was true.
This emphasizes that John told me that the girl’s/woman’s story was true. For example, the speaker is discussing the merits of the girl’s story with someone else. The sentence does not weigh in on whether the story is true or not but notes only from whom I received information about it: through John. He told me.
John said her story was true.
Orally a speaker could emphasize different words for various effects. If a speaker emphasizes John or John said, then the stress is on John vouching for the girl’s/woman/s story. The speaker could also emphasize the last word (true) and thus add weight that the story was “true” as opposed to a fabrication. The sentence says nothing about how “I” received the information.
John said, “Her story is true.”
This quotes John’s exact words. One sees this when it is written because of the quotation marks. However, if someone were stating, "John said, ‘her story is true,’ " then the speaker would audibly pause after “said,” to indicate that what follows is a direct quote. The speaker could also say, "John said, quote: “her story is true’.” The speaker could also use both hands to gesture quotation marks in the air to indicate that they are quoting John. Again, there is no information as to how “I” received the information.
“Her story is true,” John said to me.
This sentence is natural when uttered without the emphasis on “to me,” stating merely that John told me her story was true. It is not natural if the emphasis on the last words (to me). If the speaker wants to emphasize “to me,” then this phrase normally is placed earlier in the sentence: “John said to me her story was true.” Even more emphasis could be achieved by changing the verb: "John told me (or stated to me) her story was true. The verb “said” is neutral and merely indicates that John observed, noted, passed on some information. Yet using the word “told” or “stated” implies that John more deliberately, explicitly conveyed the information. An even stronger word is “declared.”
There is another possible variation. John said her story was true. He told me so.
This emphasizes that I got the information from John.
If I want to emphasize that John told me, as opposed to other persons, then I could say,
John said her story is true. He said that to me when we were talking yesterday.
By adding a clause as to when or where he said it to me (when we were talking yesterday), it emphasizes the specific context when I personally received the information. Without that clause/context, the oral emphasis would normally be placed on “said.” He said that to me.
This emphasizes that John is the one who conveyed the information.
If oral emphasis was placed on the last words (he said that to me) without any specific context, it calls attention to how startling it was that I received that information from John. For example, I know that the story is not true so the fact that John would say otherwise to me – of all persons, given what I know – is itself startling/notable/ironic/insulting. That is, somehow it does not fit or make sense with respect to my own knowledge of the facts that John would tell me the story was true when I knew that it was not.
In short, there are lots of subtle differences, depending on word order and oral emphasis. The most straightforward, common option would be, “John said her story was true.” Other variations would be used only if the speaker/author felt it necessary to add additional details.