Try to fish a relicanth,chinchou or lanturn and your first Pokemon should have the abiliy counmpounud eyes so it has 50% of finding a Pokemon holding an item. So relicanth,chinchou and lanturn are the only Pokemon that you can fish that have a chance to hold a deepseascale(5% uselly but with counpound eyes its 50%).
Lanturn(super rod) and chinchou( good rod)can be found in azur bay
Relicanth can be found in Ambrette town and cyllage city.(super rod)
Hope I helped :D