@Machomuu: In the plot, pokemon are infected by an extremely contagious virus with memetic properties, which was engineered by scientists with extremely idealist goals. After a point, Arceus removed pokemon from the earth completely in retaliation. This would've all happened before your character was born, meaning there can't possibly be any fish left. I can't really bend on this, as it's one of the biggest, most powerful reasons that humanity is really suffering. On the bright side the population has thinned so much at this point that it's actually much easier to find food than it was at first (It's still hard though. At /first/, people just starting dropping like flies after a bit. unless they hoarded some food.)
But of course I'd be happy to go over it again should you need to make a few changes.