I want to protect my circuit against reverse polarity, by simply adding two diodes in parallel between the + and - input cables. So if the polarity is reversed, the current will go through those diodes at high current and blow the fuse. Change the fuse and flip the polarity and everything should be good to go.
That kind of reverse polarity protection (i.e. based on blowing/replacing a fuse) should be used if it is "really" needed (For example, during 8 years of my automotive electronics hardware design experience, I have been asked to design such a protection only once, and it was a customer's "special request").
Anyway, you have noticed that it may not be enough to replace only the fuse. The diodes may get short even before the fuse to blow. To protect also the diodes, you can use a PTC-based Resettable Fuse. Resettable fuses heats up when a large current flows through them then they become a high-resistive element to block the current flow. They also help to reduce the inrush current drawn from the battery. RFs can be "reset" by letting them to cool down by cutting the power. Depending on the component, they can be easly cool down before you re-flip the polarity and apply again.

simulate this circuit – Schematic created using CircuitLab
Since the current drawn from the rest of circuit will flow trough the RT during the normal operation, it should be selected carefully. The environment is important, because the trip current of the RF will decrease at high-temp environments. You don't want it to block the current flow during normal operation, right?
Or...
You can use an easier and better solution as given in Voltage Spike's answer. That circuit can also be built with NMOSFETs. NMOSFETs are easier to find and cheaper.

simulate this circuit
When you first apply the supply voltage in correct polarity, the MOSFET is off, the MOSFETs gate and source voltages are undetermined. But since the current will flow through the MOSFET's forward-biased internal drain-source diode (a zener) first, the voltage at MOSFET's source terminal will be nearly zero. After this first cycle of current flow, the MOSFET's gate voltage will be higher than its source voltage. So the MOSFET will turn on and it will short the internal diode then the circuit will operate normally. That is how MOSFET allows the current to flow with correct-polarity supply. If you apply the supply voltage in reverse polarity, the internal drain-source diode will block the current to flow so the circuit will never operate. Please note that the MOSFET's breakdown voltage (VBRDSS) should be higher than battery voltage (e.g. a 40V MOSFET can be enough for your needs).