Zapdos:
Use surf before entering the rock Tunnel. You will find the Power Plant that contains Zapdos. Put it to sleep, too.
Moltres:
In the Victory road Cave with all the trainers, you will find the fire bird, Moltres. Save, sleep, and capture.
Articuno:
At Seafoam Islands, you should be able to find Articuno. Save and put it to sleep and then chuck a couple of Ultra Balls at it.
Snorlax:
Use the Poke flute after saving right next ot his fat guy. Save, Sleep, and Capture. Note: you will have two tries to catch this one.
Fossils:
you can get an Aerodactyl by going next door to the museum with CUT. At Mt. Moon you can get Omanyte, Helix Fossil, or Kabuto, Dome Fossil. you can bring them to life at the Cinnabar Island.
Eevee:
In Celadon City, go to the Game Freak tower. But take the back entrance. go to the very top and the man in the house qives you the evolution pokemon, Eevee. It can come: Vaporeon, Jolteon, Flareon. Depending on which stone you use.
Hitmonchan or Hitmonlee:
At the Fighting Dolo gym, next to Sabrina's Gym. fght all of the men and get either a kicking fighter, or a punching fighter.
Laplas:
In Celadon go to Silph Co. and you will get a Laplas if you talk to the guy who you see while you see your rival. this is a good Pokemon.