Although Gyarados has a very draconic structure, it was originally a useless fish that we all know as Magikarp. Magikarp could not fly, can't fly and will never be able to fly. Although Magikarp doesn't have much use and was even given the title the weakest Pokemon. Even his cousin Feebas didn't earn that title. What it did get credit for was it's ability to leap (bounce) it's way up over a crashing waterfall/mountain. When it has accomplished this, it evolves into the mighty Gyarados. As Gyrados it is still not able to fly as seen in the anime. Although it is seen levitating in the game, it has never been seen levitating in the anime were the Pokemon's true nature is focused on.
Gyarados is easily compared to the Leviathan. The mighty serpent of the seas." Who can catch Leviathan". It can't levitate/fly either.
It probably gets it's flying type from the fact that it can now literally leap over a whole waterfall in one atempt as seen several times in the anime. When it does so, it really looks like he is flying over the waterfall.
Another possible reason is to show the great leap/flight
improvement it has made since it was a Magikarp as you can't compare it to Gyarados.
Also as mentioned before me there are a lot of Pokemon that can't learn fly even though they are flying types. This is because of the reason that a lot of Pokemon float or jump really high in the air more then fly. For this reason they get access to bounce instead of fly such as Scyther,etc.. Genesect can learn fly for obvious reason as seen in the trailer of the 16th movie. It could probably not fly 300 million years ago since it didn't have all the features it has now that team plasma have upgraded it.