Originally posted by Gromarch:

Eat the 3 best stamina foods you have.
Use the hat if you have it.
Make as long a throw as posible, and reel in (for leveling the skill) to 6-9 meters and let it rest there until something bites.
Once something does, only reel in when it doesn't wriggle; when it wriggles, your stamina burns really fast.
Have a Stamina potion ready for that odd catch where all other tactics doesn't suffice.

This is the best response.

The only thing I can add is KEEP ANY LVL 1 PERCH YOU CATCH.

You can use them to make a small "Skilling pond" somewhere you can dig into water. Huck the lvl 1 perch in there and cast 26 feet line and reel them in. You get the same Fishing XP regardless of fish, and Lvl 1 perch take almost no stamina, even when struggling. Just be ready to go through a lot of bait to even get to 50.