Definitely a complicated question.
Neville's first wand was a hand-me-down, which was broken in the Battle of the Department of Mysteries. It was only then that his Gran bought him a brand new wand. I presume it would be from Ollivanders. By that time we're at Half-Blood Prince, so I can't see how the holly and Phoenix feather wand could have chosen Neville, because by that time Harry already had it.
My point is that Augusta Longbottom, Neville's grandmother, was an incredibly domineering woman -- regardless of the status of the prophecy, I think would have made Neville take the used wand (I believe it was his father's wand) to Hogwarts during his first year. So I'm not sure he would have had the opportunity to be chosen by the holly wand before Harry.
Events would not have unfolded in exactly the same way if the prophecy had named Neville, I don't think. He might not have survived Avada Kedavra like Harry did. Harry's and Neville's gumption manifested in completely disparate ways. Would Alice Longbottom (Neville's mother) have put herself in between Neville and Voldemort? I'd like to think so. And this aspect is essential to the connection between Harry and Voldemort -- Lily's sacrifice.
The canon answer seems to be: It can't be known whether or not Neville would have been had Harry's experience as The Boy Who Lived. Thus, it can't be known whether the twin to Voldemort's wand (the holly/Phoenix feather wand) would have chosen Neville.
Neville’s childhood had been blighted by Voldemort just as much as Harry’s had, but Neville had no idea how close he had come to having Harry’s destiny. The prophecy could have referred to either of them, yet, for his own inscrutable reasons, Voldemort had chosen to believe that Harry was the one meant.
Had Voldemort chosen Neville, it would be Neville sitting opposite Harry bearing the lightning-shaped scar and the weight of the prophecy ... or would it? Would Neville’s
mother have died to save him, as Lily had died for Harry? Surely she would ... but what if she had been unable to stand between her son and Voldemort? Would there, then, have been no ‘Chosen One’ at all? An empty seat where Neville now sat and a scarless Harry who would have been kissed goodbye by his own mother, not Ron’s?
Half-Blood Prince - pages 133-134 - Bloomsbury - chapter 7, The Slug Club
ETA: A related question maybe: Would Neville Longbottom have survived if Voldemort had marked him for death?