If I have a hundred dice, and I roll them all, there are a large number of possibilities. 6^100, to be exact. But even though this number is very large, that doesn't mean that it is impossible to get any particular combination. If I roll all the dice, I have to get some combination, even if that combination is extrememly unlikely.
Another way to think about it is like this: If I paint a picture, there is a virtually infinite number of ways I could make my brush strokes, so there is a virtually infinite number of different paintings I could paint. But that doesn't mean it is impossible to paint a painting.
I don't see why mutation and natural selection are not likely to produce anything useful, in your opinion. I think we have to agree on a definition of "beneficial mutation". I would define it as one which increases an organism's biological fitness, which is the ability of that organism to reproduce effectively. There many kinds of beneficial mutations - they could protect against disease, or help an animal evade predators so it can live long enough to reproduce, or the mutation can increase the number of offspring, or even lower the number of offspring, if these offspring are then more likely to grow up and reproduce. It could also do something more subtle, like allow for a particular nutrient to be absorbed in a new way, so the mutant is less likely to die of a deficiency in this nutrient.
In the case of birds, mutations in genes which affect scale growth could have resulted in downy feathers, which kept dinosaurs warm. These may have only been present when the dinosaur was young. Other types of feather, such as contour feathers, may not have started out as particularly aerodynamic. They may have been much smaller in relation to the whole animal, and they may have covered only the forelimbs. These could be useful in mating displays, in much the same way birds of paradise have elaborate displays which mainly show off their feathers. They could have grown longer, as peacock tails have, into something that improved agility on the ground and even could have been used for gliding. From there, gliding developed into powered flight which we see in modern birds.
This is an outline based somewhat on my speculation, but experiments have indicated that feathers are modified scales, and a number of fossil species have been found with impressions of feathers. Some could fly, some could not. Caudipteryx had long feathers on its forelimbs and tail, but does not appear to have been able to fly. These feathers may have been used to attract mates or for some other purpose. There also seem to be some dead ends - for example, Microraptor gui appears to have had four wings. Its fore and hind limbs had long feathers. You can think of this as another way birds could have turned out, with four wings instead of two, but for some reason, this didn't work out.