The small bluestreak cleaner wrasse (Labroides dimidiatus) will approach a much larger fish (for example a grouper such as Cephalopholis miniata), enter its mouth, and spends several minutes cleaning its teeth. How did this behavior evolve? Wouldn’t the first cleaner wrasse that was bold enough to approach a larger fish have been immediately eaten? Since, in this encounter, the behavior of both fish isn’t learned, it must be encoded in their genomes. How could the appropriate coding gradually evolve?
Cleaner wrasse don't only clean within the mouth; although some species may specialize towards mouth-cleaning, it's likely that this behavior began with cleaning elsewhere on the fish's body.
Some studies (e.g. Bshary, 2003) suggest a large effect of cleaners on fish populations/diversity, so it seems that there are strong selective pressures for evolving behavior permissive to cleaning fish.
The cleaners themselves seem to have evolved cleaning traits on many occasions (see Baliga & Law, 2016). Although there are some obligate cleaner species, it's more common for cleaners to clean as juveniles, and the most common transition between cleaner behaviors is from non-cleaners to juvenile cleaners.
Therefore, it seems like the first cleaners were very small fish outside the typical prey target size of the cleaned fish. If there is strong selection towards individuals who tolerate these small, non-prey cleaners, it's reasonable to expect that this behavior could expand towards larger cleaners, and eventually to the more extreme versions of the behavior like allowing cleaners in the mouth.
Baliga, V. B., & Law, C. J. (2016). Cleaners among wrasses: phylogenetics and evolutionary patterns of cleaning behavior within Labridae. Molecular phylogenetics and evolution, 94, 424-435.
Bshary, R. (2003). The cleaner wrasse, Labroides dimidiatus, is a key organism for reef fish diversity at Ras Mohammed National Park, Egypt. Journal of Animal Ecology, 72(1), 169-176.
The behavior is beneficial for both species. To use your explanation, perhaps the first L. dimidiatus that was bold enough to approach C. miniata was immediately eaten, but some proportion of C. miniata did not eat the L. dimidiatus, and the alleles responsible for the cooperative behavior increased in frequency for both species, while the alleles responsible for the non-cooperative behavior decreased in frequency.