From your question: "... only "reshuffles" alleles, and doesn't generate new ones (...). So why does it create genetic variation?"
There are no trick questions, still my answer goes:
Because genetic variation is also created by independent assortment.
There are two ways of crossing-over in meiosis.
First, there is Chromosomal crossover, or crossing over, which "is the exchange of genetic material during sexual reproduction between two homologous chromosomes' non-sister chromatids that results in recombinant chromosomes." (Wikipedia)
Second, however, there is, much lesser known Independent assortment of chromosomes:
"The physical basis of the independent assortment of chromosomes is the random orientation of each bivalent chromosome along the metaphase plate with respect to the other bivalent chromosomes. Along with crossing over, independent assortment increases genetic diversity by producing novel genetic combinations."
Without alleles being changed (if exchanged, as a result), chromosomes from on parent are exchanged with (homologous) chromosomes of the other parent. This, too, results in genetic variation, and - as such does not involve so called crossing over of allelic genes. Exchange of alleles as a result of independent assortment must be distinguished from creating new alleles by crossing over,i.e. exchanging genes or parts of genes.
Independent assortment can be differentiated from "allelic variation". Hermaphrodite reproduction as sexual reproduction shows that in one single individual there are a million combinations of alleles. By definition, however, not all alleles existent in a population. Interestingly, this rule is not valid in respect of the rather unknown mechanism of mingling of chromosomes (not alleles). Any indivual has got the potential to find any - among all - combination of chromosomes.
From this finding results that intercourse of different individuals in contrast to hermaphrodite interchanging of chromosomes and alleles can be distinguished by potenitally combining all alleles, whereas all chromosomes can - potentially - combined by one hermaphrodite individual.
Surprising about this answer is that, in the words of your question, "new genetic variation" that is not considered allelic variation as it does not involve the changing of genes is thus produced by sexual reproduction.