Get your fishing to 85 like you said you would with sharks. Then powermine iron to 80 mining, then do LRC for some good cash. After that, spend that cash on firemaking 99 and smithing/crafting. Next, get 99 thieving by doing master farmers (you earn money by picking seeds). Spend the money on herblore/stake with it.