The website The Cave of Dragonflies has a well-written and exhaustive explanation of the Gen I capture mechanics (with a conclusion written in simple terms). The main points relevant to the Living Dex challenge are as follows:

• Every Pokémon species has a catch rate: the lower the number, the harder the Pokémon is to catch. In general, rare Pokémon have a low catch rate while common Pokémon have a high one.
• Any status effect increases the odds of a successful capture with sleep and freeze being the most effective.
• Ultra Balls benefit greatly from low catch rate, low HP and status effects.
• Against a Pokémon at full health with no status effects, a Great Ball is better than an Ultra Ball.
• The low HP threshold for maximum catch chance is 1/2 HP for Great Balls and 1/3 HP for Ultra Balls.

From this, we can make the following set of rules:

• Against common Pokémon, throwing a Great Ball at full health, while not having the highest catch chance possible, is the most efficient. Only go for sleep if you have guaranteed initiative with 100% chance to hit.
• Against rare Pokémon, doing damage, using sleep and throwing an Ultra Ball guarantees the highest catch chance possible. Lowering the HP to less than 1/3 does not increase the catch chance further.
• Against Legendary Pokémon, using sleep and throwing Ultra Balls is the most efficient. The extra catch chance gained from lowering HP is marginal.
• For most encounters, if you do not plan on doing damage, going with a Great Ball is your best option, status effect or not.

Rare Candy locations

Considering many Pokémon can only be obtained via level-up evolution, picking up Rare Candies while going through the story can speed up the experience grind quite a bit. Here is the list and location of all the Rare Candies in the game:

• Mt. Moon - 1F, southeast corner
• Cerulean City - (Hidden) Center of the northwest house's backyard
• S.S. Anne - 2F, 4th room from the left
• Rocket Hideout - B3F, east side of the maze
• Route 17 - (Hidden) Middle of the patch of grass in the Cycling Road
• Pokémon Tower - 6F, west area
• Silph Co. - 10F, southwest room
• Fuchsia City - Warden's house, behind the boulder
• Power Plant - Northeast area
• Pokémon Mansion - B1F, northern area
• Pokémon Mansion - (Hidden) B1F, northwest corner of the area with the Secret Key
• Victory Road - 1F, north area
• Cerulean Cave - (Hidden) 1F, on a rock in the southwest area of the floor

HM locations

• HM 01 (Cut) - S.S. Anne
• HM 02 (Fly) - Route 16
• HM 03 (Surf) - Safari Zone
• HM 04 (Strength) - Fuchsia City
• HM 05 (Flash) - Route 2

Fishing Rod locations

• Old Rod - Vermilion City
• Good Rod - Fuchsia City
• Super Rod - Route 12

There is no way to get Mew legitimately anymore, as the only way was to get it through an event. Fortunately, it is possible to make use of a glitch that forces a random encounter against a wild Mew. There is an in-depth article about the Mew Glitch on Bulbapedia. In short, you need to respect these criteria:

• Having access to Fly or Teleport
• Not having fought both the Gambler on Route 8 and the Youngster on Route 25 (slow version)
• Not having fought both the Jr. Trainer ♂ west of Nugget Bridge and the first Swimmer in Cerulean Gym (quick version)

The slow version allows you to trigger the glitch whenever you want as long as the 2 optional encounters are skipped. The quick version of the glitch relies on you catching an Abra before fighting Misty. It is more restrictive, but you can get the Mew encounter as soon as you access Route 24. Remember to save your game before you attempt any version of this glitch, in case something goes wrong. Good luck!