12.5 volts should be plenty for an engine start. A fully charger battery is about 12.9 volts - unless on a shore charger. And a voltage check at the starter won't really prove much either. If there is a bad ground there could be good voltage at the starter but when you turn the key the current can't flow. Check all connections between the battery and starter, take apart and clean, and then try again.
Living aboard in Victoria Harbour