It's actually very easy to level up Fishing, in bite-size pieces. It does require an initial time-sink, but Alliance at least have one Fishing Quest in Auberdine to ease the boredom first time around. If you're also skilling up Cooking then Fishing is the perfect compliment. When you first learn Fishing you should spend the 20 minutes or so it takes to get Fishing to 50, then immediately learn Fishing (150). Also spend money on the lures. You don't need to buy a stack of them; just buy one or two at a time. Missed fish do not increase your Fishing Skill so you should always have a Lure to reduce the number of fish that get away.

Once you have Fishing at 50 or more, every time you're riding down the coast or alongside a river and you see a school of fish, stop and throw out a line and fish the school out. Every time you find yourself waiting for a ship (Alliance again have the advantage in not having Zeppelins; hard to fish from a Zeppelin) throw out a line. When the ship arrives, board it and run to the other side and throw out a line. You can sometimes catch another 2 to 3 fish while waiting for the ship to sail.

Is your Guild doing Onyxia? Don't just run to the cave and stand around waiting for everyone else to arrive. Find a nearby lake or the closest beach and go Fishing.

I don't have the Tacklebox Addon either (and never did). I just have my Fishing Pole and Weapons Hotkeyed, as well as the Fishing Skill. Time to Fish? Hit the Fishing Pole Hotkey, then the Fishing Skill hotkey. Got a Bite? Shift & Right Click is your friend. That's all it takes.
Fishing Skill Hotkey
Shift & Right Click
Fishing Skill Hotkey
Shift & Right Click

Now maybe Tacklebox reduces it even further by Autocasting and Autocatching your fish...but what are you? A Troll or a Bot?

It's only Fishing, not Rocket Surgery.
 

My honest suggestion: when you've got a night you want to spend in without spending a lot, set down with a couple of drinks and a podcast/phone/SO who plays WoW, and get toasted fishing.

I've got two chars who are 300 fishing. *grin* The extream Angler from Hinterlands is nice-- and several of my friends have killed attempted gankers with it. (usually while toasted and not noticing until it's over; in the rogue's words, "oh, that's my my specials didn't work.....")
 

If the priest is only half as bad as the forums are suggesting, then I will be leveling fishing. Call it the nerd or geek in me, but all of my skills must be maxed for me to feel complete.

As John mentioned, it's actually VERY easy to level and if you do cooking at the same time, even better. I have a little trick that worked well. Put on your favorite DVD or line up of shows. Turn all of the sound off in WOW except for ambient which you turn up very high.

Look at the WOW screen to cast and position your mouse over the bobber. Now you can watch tv and just right-click when you hear the splashing water to retrieve the fish. Rinse. Repeat.