There will be 3 roaming legendary Pokemon that you may encounter. They are based on the 4 gods of direction.

You will find them walking around, when they spot you they will take off, if you do not begin a battle within a certain time they will despawn and relocate.

They are not locked out of being shiny. As long as you do not start the battle with them they have a chance to respawn somewhere as a shiny. Once you start a battle while they are shiny they will stay that way.

To start this quest you must first capture Meteodaina who will be hidden somewhere in the post game.
Although there is a way to begin this quest before post game. Very rarely Meteodaina will be roaming around the over world and can be captured. It is only after you beat the elite four and begin the post game that it is found resting in its hideaway.