You found a heart!
Ok, answering time.
Solution to Trick House puzzle: (It's the highlighted S)
List of legendaries:
Celebi: Get the GS Ball in your trip to Kanto. Beat L.T Surge (Vermillion) and Sabrina (Saffron). Now call Prof Elm from a Phone Booth and go to Vermillion to take the ship to Johto. Talk to Prof Elm in New Bark, and then go to Azalea Town and talk to Kurt. Walk a little, and he will give you back the GS Ball. Now go to the Ilex Forest. It's in level 30.
Raikou, Suicune, Entei: Go to Burned Tower in Ecutreak and fall on the basement floor from a hole. When they have awakened, they will be around all Johto. It's just luck.
List of starters: (in order of apparition) (all are catchable)
Charmander: Goldenrod City Game Corner, 2100 coins.
Treecko: Go to the hole in the rails in National Park. You will see two paths. Go to the rigth, near the East door. You will see a path between the trees. Enter and beat the trainer.
Squirtle: In New Bark Town, surf in the little part of the water route. If you go to the next route, you won't find it.
Torchic: Go to Lavander Town and to the South. You will see another path between the trees which leads to a cave with a guy who gives you an egg. In that cave, you will find wild Torchics. The egg has a random baby poke.
Bulbasaur: Go to the grass zone (Area 3) in the Safari Zone. It's wild there.
About Beldum... I think that there is no way yet.
(Told you this was a good idea, zel)