Is there a good definition of magic which does not rule out the existence of
It's an interesting question, and I think it's best considered the context of times and settings in which the idea of magic was taken seriously. I also doubt that there's a lot to be gained by looking for a full-blown definition, but we can learn something by looking at broad commonalities.
First on the bit about magic words and rabbits. If it turned out that saying the right words in the right way could make rabbits appear in hats, then we would have discovered a new regularity in the world, though whether we had discovered a new law of physics is a lot more doubtful. After all, the regularities of the special sciences aren't usually classed as laws of physics, even though physics has to be consistent with them.* We might want to say that this regularity is "natural" because all the events take place in nature (saying the words, the rabbit appearing...) but it wouldn't follow that it wasn't magical. Older notions of magic explicitly included a concept of natural magic.
What counted as "natural magic?" There's no tidy answer, but part of the background was the idea of an "occult quality." "Occult" here means "hidden." The behavior of lodestones (magnets) would have counted as a case of natural magic on some views. From the point of view of Renaissance thinkers, the operation of the lodestone depended on hidden properties. It also acted over distances, which tended to be characteristic of things that were labeled magical.
Neoplatonic thought had room for a concept of magic. The reason was that everything was in contact with everything else by virtue of everything being contained within/infused with the World Soul.
Was this a religious idea? There's no easy answer. It wasn't associated with any particular religion, but it clearly had a strong kinship with ideas that we think of as religious.
Some particularly important magical ideas were bound up with astrological beliefs. Belief in "astral influences" was very common in the ancient world and in the Renaissance. Some of these influences were considered benign. The Renaissance neo-Platonist Marsilio Ficino wrote quite charmingly about the things one needed to do to capture these beneficial astral influences—particularly the solar influences. But there was nothing especially "religious" about these beliefs. They were part of a broadly accepted view of how nature worked.
Some astral magic was more problematic. It called for commanding not-merely-human beings to do one's bidding. This was "demonic" magic. Were the demons supernatural? There's no good, simple answer. They were one of the kinds of things taken to populate the world, but their realm was the super-lunar—beyond the moon. The Church certainly objected to demonic magic, but one could believe in the existence of the beings themselves whether or not one was a Christian.
A good deal of what we might call folk magic didn't have much in the way of theory about it at all. My mother told a story of having had a wart removed from her hand by having it "charmed." In one version of the wart charm, the charmer would "buy" the wart for a penny. Many people believed that this worked without any particular view about how it worked. But they would likely have been willing to call it magic.
All this is just the tip of a large and very fascinating iceberg. But the most important lesson to draw is that there neither is nor ever was a single, unified conception of "magic." Magic is an excellent example of a "family resemblance" notion. Furthermore, many magical ideas existed against a background of broader views about the cosmos that have either faded entirely or exist only in attenuate from among contemporary, educated people. But even here we need to be careful. There are thoughtful, intelligent twenty-first century people who would tell you that they believe that there's such a thing as magic. Such people tend to believe more broadly that the mind can influence matter in ways that you and I might reject. However, many of these people wouldn't see any necessary conflict between their own views and science. Their particular views about science might be mistaken (for example, might include misunderstandings of quantum theory) but it wouldn't be because what they believe is somehow essentially incompatible with science.
Occasionally I'll hear philosophers trying to make claims about the concept of magic. My experience tends to be that what they say is crude, ahistorical and far too simple. If you want to get an idea of what it would be like to be a contemporary believer in magic, I'd highly recommend Tanya Luhrmann's book Persuasions of the Witch's Craft. It's a rich ethnographic study by a philosophically-informed anthropologist. And if you'd like a better understanding of magical ideas in the Renaissance, you might want to have a look at Frances Yates' The Occult Philosophy in the Elizabethan Age, among other of her works. Yates' scholarship certainly has its critics, but it's hard to read her work without getting a glimpse of a much richer idea about what "magic" might once have meant.
*Notice, by the way: I didn't say that the upper-level laws need to be consistent with physics. If we discovered a new psychological regularity that didn't fit with what physics tells us, then if the regularity really was stable and robust, it would represent a problem for physics, not for psychology. The regularities are what they are.)