Well, in Gold you can duplicate items. Of course, you might not want to do it that way. :P In any case, Lugia is insanely hard to get at Lv 70 (for me anyways,) so you might not even want to use the legitimate Master Ball on one of the beasts.
Anywho, to encounter them, I'd go to two adjacent Routes like the two West of Ecruteak by the Moomoo farm, or the two south of Ecruteak. Get twenty or so Max Repels and a Pokemon in the high 30s. Save on one side of the division between two routes, use a Max Repel, and walk around. Once it's used up, use another. When that one's sone, cross over to the next Route and use two more, then back to the Route you started on, use two more...ect. If you run out, just turn the game off and do it again. You should run into one of them within the fifth try.
Now that you have data, you can encounter then again faily easily. Remember that every time you enter a building, leave a building, or enter/leave a route/city, their location changes. Go to Mahogany because it is surrounded by three routes that they tend to visit often, and two of the three routes do not have guardhouses that force their locations to change twice when you try to approach them. Check your Pokedex and if they're about two routes away, head toward them hoping that they'll move toawrd you and you'll end up in the same route. Or if they're only one route away, head to one of the other routes surrounding the town. This method worked immensely well for me.
Get a buttload of Ultra Balls, at least 10 Heavy and Fast Balls, and if you've beat the game and have a Level 60+ Pokemon, some Level Balls as well. First get something in the level 35-40 range with False Swipe that is very fast (Scyther works nicely, but give it the Quick Claw just in case.) After several encounters, you'll get them to 1 HP.
Now is the hard part. On your next encounter you could just toss a ball the second it shows up, but that doesn't work too well. Get a fast Pokemon under level 40 with a sleep move and give it the Quick Claw. The second you see the beast, use the sleep move. If you get the first turn and you can get it asleep before it runs away, start tossing Ultra, Heavy, or Fast Balls. OR, switch to a very high level Pokemon and use Level Balls. If it wakes up before you catch it, you may have another chance to put it to sleep before it runs away. Several times, Entei actually battled me for a few turns before running away. It's all luck though--if it leaves, just run into it again.
Hope that helps.
~Chibi~