Survival Of The Fittest Challenge

Interestingly enough, for Pokemon that have HP-recovery (not HP-draining) moves, the Old Rod is the single most valuable item in the game. It allows summoning (with 100% reliability in Gen 1 and decent reliability in later generations) of an enemy that does not deal damage, so that HP can be guaranteed to be full at the end of the fight, enabling use of a PokeCenter. Magikarp thus become the world's weirdest PP-replenishing items. Also, due to a quirk in programming in Gen 1, they may be summoned from the water in Lorelei's room.
(Before Old Rod, Harden-only Bugs are equally useful.)

Important moves:
Rest can be taught to essentially any Pokemon that can use TMs. The problem is the location. Kanto's is S.S. Anne, Johto's is Ice Path, Hoenn's is Lilycove City, Sinnoh's is Veilstone City, Unova's is Castelia City, and Kalos's is Hotel Cyllage. Learning Rest grants one Pokemon the ability to regenerate full HP at the cost of passing out for two turns, which means it probably won't be at full HP at the end of the Rest unless the enemy can't deal damage for one reason or another.

Leech Seed cannot be learned via TM, and has the slight issue that the drain is proportional to the enemy's HP. As such, a Magikarp won't be much use for healing your L50 Venusaur. On the bright side, the enemy can faint from it, so draining a sleeping or minimal-damage enemy may result in fully-healed HP. Bulbasaur can abuse this early on by landing Leech Seed and then Growling an enemy's Attack down until it deals hardly any damage.

Milk Drink is extremely valuable and is a Miltank/Skiddo line exclusive. Since healing moves aren't banned, it should be usable to restore Pokemon HP in the field. Mind, Miltank/Skiddo then has to heal itself to full, but it can potentially be used to drag the team's HP back up to full for a PokeCenter run.
Chansey's Softboiled has similar uses.

Absorb is a weak draining move... which nonetheless makes for a good HP boost in Rock/Ground-heavy areas like Tunnels/Caves/Mountains. Many Grass-types can abuse it... and Kabuto, Beautifly, Frillish, and Goomy.
In RBY, its superior cousin, Mega Drain, may be learned by essentially all Grass-types via TM... and by Butterfree, Beedrill, Ekans line, Zubat line, Venonat line, Tentacool line, Grimer line, and the Gastly line. I particularly recommend the Gastly line due to its high Special, which compensates for the absence of STAB.
In Gen II-IV, its far super cousin, Giga Drain, may be learned by several more Pokemon. Unfortunately for Johto players, it's only available from Kanto...

Dream Eater is a powerful move that only works on sleeping Pokemon. In Gen 1 it's limited to Gastly line naturally and Drowzee line by TM (Viridian City, requires Cut to obtain), in Gen 2 is expanded to Hoothoot line extremely late, and in Gen 3 is extended to Ralts line similarly late. Gen 4 adds two Legendaries and Gen 5 adds Munna at L41. TM learn-lists after Gen 1 are a bit more versatile, but Gen 2's Dream Eater TM only comes in Viridian City...

Pay Day is not a recovery move, but is the only thing that can recover your CASH. (After Gen 3, Persian does not learn it, so delay evolution to L30!) It's available to multiple Pokemon via TM16 in Gen 1. Keep in mind that Meowth is only available pre-E4 in Blue, Silver, Crystal (nighttime), FireRed/LeafGreen, and SoulSilver.

Generally speaking, blow all your money on Revives and Pokeballs. The ONE major exception I can think of is Gen 1's ignores-accuracy-check X Accuracy and possibly X Speed -- Haunter can use this to land 100%-hit Hypnosis on a slew of enemies, and Hypno can do the same after enough X Speeds (if it survives long enough).

Alternatively, if you are not in Gen 5, teaching a TM will give you the move with full PP. Potentially, blowing money on, say, Mega Kick TMs would allow you to restore the PP of that move for 3000P a shot by repeatedly re-teaching it. This may be abusing mechanics, though...