You can also trade a Minccino (can be caught in a variety of places, or it cal be evolved) for a Basculin (nicknamed Blueye) at level 25 from a boy called Kyle in Driftveil City (his house in the house to the right of the house directly in front of the Pokemon centre). He is in the same house as the old man who gives you a shell bell.
I did this trade in Summer, so I'm not sure whether it works in other seasons. Occasionally, he will offer to battle you with his Minccino. I haven't battled him yet, so I'm not sure if you need to have Blueye with you.