changing the trendy saying only re-randomizes which spots feebass can be found in. there is no actual sure way to figure out which spots these will be.
when I first went hunting for it I fished up 3-4 Pokemon per water tile to make sure I found him, tedious I know but it works.
luckily any rod can be used to find it so you can do this while mostly only encountering low level magicarp if you use the old rod.