The best place to start fishing is Darkshore. Look for Gubber Blump and do the quest
The Family and the Fishing Pole. Start there and work your way up.
Besides fishing, consider Wondroustremor's
money making tips. I hesitate to tell you to change professions, but leveling herbalism or mining would be a moneymaker for you. Could you stand to lose the leatherworking, since you are fairly low on that? Honestly, with what you can make on the other gathering professions, you could buy gear after you get your mount.