I know Genesect and Golett/Golurk can learn Fly. But what are some others?
Depends on what you think can fly or not. Here is a list of them. I think Doduo because it has no wings and Mew, but it can learn everything so... yeah.
Arceus can, and so can Rayquaza (I know it's Flying type, but I don't think it looks like it).
This is slightly opinionated but here's my take on it, as of Gen 7
Pikachu (ELE) Doduo (NOR/FLY) Dodrio (NOR/FLY) Mew (PSY) Giratina* [Origin Form is wingless] (GHO/DRA) Golurk (GRO/GHO) Volcarona (BUG/FIR) Genesect (BUG/STE) Drampa (NOR/DRA) Tapu Koko (ELE/FAI)
Debatable: Hoothoot - wingspan is so small that it doesn't look feasible Kyurem - same problem Vullaby - same problem Rayquaza - wingless, but a legendary with a connection to outer space, and one might venture that it could fly going solely by appearance in this case Arceus - no wings, but it's pretty much God, so not on my list Celesteela - extremely heavy pile of metal, but the base of its body and arms resemble rocket launchers