The Legendary Birds are stationary legends in FRLG, so they can be caught as soon as you reach their respective locations.
Arcticuno is at the Seafoam Islands.
Zapdos is at the Power Plant
Moltres is at Mt. Ember off of One Island.
Each of their locations require surf to reach, which is only usable after beating the gym at Fuschia City (the HM itself can be found in the Safari Zone). Good luck and happy catching!