Ardenweald should give you SL fishing, you should be able to learn the skill in Oribos.
You have trained/learnt fishing for each of the expansions?
Draenor was slightly different because you had to fish it up/loot it. Unllike other expansions where we just went to a trainer for that expansion.
Draenor Fish
To get started, you’ll need to loot Fishing Guide to Draenor–either from looting mobs or from fishing in Draenor. It puts your maximum skill cap up to 700, even if you’re at level 1.