Throughout Harry Potter, we see the Killing Curse used constantly by ne'er-do-wells. We are later told that using it damages the soul, and this damage is what makes Horcruxes possible. However, if we are to think of it as flinging a part of one's soul at an enemy (as it appears to be; Harry retained a piece of soul shrapnel lodged in him), should the soul not also be damaged when it misses, IE when Voldemort destroyed the centaur statue in the Ministry of Magic?
It seems doubtful that this would damage the soul
I think you've misunderstood how the soul-splitting process works; all signs point to the act of murder being the thing that breaks a soul, rather than the Killing Curse specifically; Slughorn tells us, for instance (emphasis mine):
[T]he soul is supposed to remain intact and whole. Splitting it is an act of violation, it is against nature."
"But how do you do it?"
"By an act of evil — the supreme act of evil. By committing murder. Killing rips the soul apart.
Harry Potter and the Half-Blood Prince Chapter 23: "Horcruxes"
Although the Killing Curse is, as the name implies, the most expedient way of committing murder, it certainly isn't the only one; as kviiri reminds me in comments, at least two of Voldemort's Horcruxes were created from murders by other means:
Myrtle Warren, used by Voldemort to turn the diary into a Horcrux, was killed by the basilisk in the Chamber of Secrets:
Myrtle swelled importantly, her face shining. "I died."
"How?" said Harry.
"No idea," said Myrtle in hushed tones. "I just remember seeing a pair of great, big, yellow eyes. My whole body sort of seized up, and then I was floating away..."
Harry Potter and the Chamber of Secrets Chapter 16: "The Chamber of Secrets"
Hepzibah Smith, used to turn Hufflepuff's Cup into a Horcrux, was poisoned:
"[Smith's House-elf] remembered putting something in her mistress's cocoa that turned out not to be sugar, but a lethal and little-known poison," said Dumbledore. "It was concluded that she had not meant to do it, but being old and confused —"
"Voldemort modified her memory, just like he did with Morfin!"
"Yes, that is my conclusion too," said Dumbledore.
Harry Potter and the Half-Blood Prince Chapter 20: "Lord Voldemort's Request"
Likewise, as Adamant remarks in a comment on the question, casting the Killing Curse doesn't throw around a bit of your soul; what happened to Voldemort was a rather unique case.
Judging by Slughorn's statement, it seems as though the intention to commit murder isn't enough. That seems fair; Harry intends to commit murder on a couple of occasions (against Snape at the end of Half-Blood Prince, for example), but by the end of the series his soul is still perfectly intact.
So, although we can't be absolutely certain how the magic would react, it seems most plausible that your soul is only damaged if you actually succeed.
Actually it seems that it does not, at least in the opinion of very clever wizards who knew quite a lot about the dark arts (spoiler alert):
Snape himself thought that it would not damage his soul when he used it to kill Dumbledore. He agreed to it when Dumbledore asked him for this "one favour", and he actually carried it out.
The relevant conversation was (emphasis mine):
"If you don't mind dying," said Snape roughly, "why not let Draco do it?"
"That boy's soul is not yet so damaged," said Dumbledore. "I would not have it ripped apart on my account."
"And my soul, Dumbledore? Mine?"
"You alone know whether it will harm your soul to help an old man avoid pain and humiliation," said Dumbledore. "I ask this one, great favour of you, Severus, because death is coming for me as surely as the Chudley Cannons will finish bottom of this year's league. I confess I should prefer a quick, painless exit to the protracted and messy affair it will be if, for instance, Greyback is involved - I hear Voldemort has recruited him? Or dear Bellatrix, who likes to play with her food before she eats it."
His tone was light, but his blue eyes pierced Snape as they had frequently pierced Harry, as though the soul they discussed was visible to him. At last Snape gave another curt nod.
Dumbledore seemed satisfied. "Thank you, Severus..."
It implies that the intention behind the killing determines whether or not it maims the soul. Intriguingly, it also suggests that mercy killing is not damaging to the soul in the HP world.