I don't think magic is necessary for fantasy. You could write a story about someone from a culture of your own invention, with a different worldview and level of technology from your own, and no magic at all--and it would be perfectly legitimate as a work of fantasy.
You could write about a foraging society, living in the middle of a vast savanna. It's not in Africa, or any place on Earth that we can recognize; it's an invented world. They have a social structure and cosmology based on their experiences as nomadic grassland-dwellers, moving with the seasons (and what are those seasons?). They have vague ideas about the world beyond the grassland, but most of it is secondhand information, so they have superstitions about it. They have a religion, and they practice certain rites, and maybe some people have visions, but what they do isn't really magic.
The protagonist is a member of this society, and s/he must undertake a journey to the forest or the ocean--which no one among his or her people has ever seen (or if they've gone to look for it, they've never returned).
You could build this entire fictional universe, set one person's quest within it, and it would be fantasy. Without magic. Without swords, even.
You could even write a fantasy novel about rabbits, who must find a new home after their old warren is destroyed.
As Preyer pointed out, these won't fit into certain genres of fantasy, but what book fits into every genre?
And oh, yes--you can definitely have fantasy without dragons, fairies, gnomes, dwarves, and the like. I'm writing contemporary and urban fantasy that includes none of these creatures.