Good comments by the others. Seconding Sarcher's comment, attempting to define "the lowest gain that a moving coil stage of a phono preamp should have" for a particular cartridge is risky, because different phono stages that provide the same amount of gain can differ widely in how much noise they generate in doing so. Also, comparing signal-to-noise ratio numbers for different phono stages is often an exercise in futility, because S/N specs are not consistently defined in terms of reference levels, and in terms of whether and how they are
"weighted".
Also, the sensitivity of your power amplifier (the input voltage that is required to drive it to full power) is a factor to consider. If it has particularly low sensitivity, meaning a high sensitivity number, if the sum of the phono stage and line stage gains are too low you may not be able to drive the amp to full power even with the volume control at max.
My suggestion is simply that after coming up with a preliminary list of candidates, try to determine if others have used each of them successfully with the particular cartridge, or at least with similarly specified cartridges.
Regards,
-- Al