Cardio 101, Sexual Trex and Iron Gut are three perks I generally get pretty early on for stamina. If you melee a lot, or like mining or whatever, Pummel Pete/Miner 69er are good yeah. Red Tea is gold, and always try to keep coffee on hand.
IIRC if you drink coffee+red tea with 1 point into cardio 101 you have very very slow (almost non-draining) stamina drain.