This is a problem only with fish that are relatively high on the food chain (such as tuna), as each rung on the ladder effectively acts as a multiplier for heavy metals accumulation. Also fish that are high on the food chain are usually caught older (larger) so they've had much more time to accumulate heavy metals (I just today saw a headline saying "the snapper you're eating may have been 60 years old"). You could live your whole life eating nothing but canned sardines (which are caught young and small) and you'd never have a mercury toxicity problem (at least with the levels of mercury contamination in the oceans today).

Another thing is that fish oil supplements do not seem to suffer any heavy metal contamination; partly because the fish used for this purpose happen to be low on the food chain, and partly because of the way the fish oil is processed. There have been a couple of studies where they actually tested more than a dozen common (i.e. supermarket availability) fish oil supplements and found zero mercury or other heavy metal contamination in most of them and only insignificant trace levels in one or two IIRC.