Yes you can buy kosher fish in a non kosher fish store provided there are still some scales on the fish. If the fish has been completely fillet then you do not know which fish it really is.
The reason you do not need to be concerned with the knives being used is because you wash the fish again after you bring it home (Darcho Behadacha)