So for polarity reversal causing no damage and requiring no fuse replacement you can use pretty much whatever diode you want and put it in series so that "normal" current flow passes through the diode only if properly plugged in. With the current requirements and voltages that you're working at, this shouldn't be an issue. A simple silicon diode should be fine.
For overvoltage you're going to want a circuit more like what Nick Alexeev suggested in the comment. Essentially a zener diode with a PTC or other type of fuse. The Zener should have a value which is less than the maximum input to your regulator.
So basically, if you reverse batt_in+ and batt_in- the first series diode will prevent any current from flowing and protect your circuit. If batt_in is greater than the breakdown voltage of the zener, it will start pulling down a lot of current, and blow the PTC fuse.
The only extra thing you might do, is to guarantee that the startup current doesn't exceed your PTC's current limit, you can place a resistor on "protected V_IN+" or "protected V_IN-" (in series before the regulator and decoupling capacitor) such that:
(BATT_IN+ - V_forward_diode - Resistor*Maximum_expected_load) >= Vmin_regulator
For the desirability of any specific characteristics for the PTC, the diodes, and everything else, it all depends on your application. In general, I tend to wing it unless I have a real reason to crunch the numbers. I'm also a bit too tired (on my way to bed) to really get into how to calculate what these values should be, but if you need this info ask in a comment and I'll post some tips on getting the numbers.
Though, why not just use a polarized connector for the batteries so that you don't have to worry about whether the connector is plugged in backwards? And in what context are you going to overvolt? Think about these questions too when trying to answer a more complicated design choice (a polarized connector is easier than adding an extra diode, and is less likely to lead to extra design considerations).
Hope that helps!
Try this IC:
http://www.linear.com/product/LT4356-1
LT4356-1 and -2 - Surge Stopper
Features
Stops High Voltage Surges
Adjustable Output Clamp Voltage
Overcurrent Protection
Wide Operation Range: 4V to 80V
Reverse Input Protection to –60V
Low 7μA Shutdown Current, LT4356-1
Adjustable Fault Timer
Controls N-channel MOSFET
Shutdown Pin Withstands –60V to 100V
Fault Output Indication
Guaranteed Operation to 125°C
Auxiliary Amplifier for Level Detection Comparator or Linear Regulator Controller
Available in (4mm × 3mm) 12-Pin DFN, 10-Pin MSOP or 16-Pin SO Packages
You should note that the previously commended LT4361 IC is similar but does not support your input voltage range requirements; many ICs out there are intended to support protection of low voltage supply buses, less support the higher voltage ranges you seek.
LTC4361-1/LTC4361-2 - Overvoltage/Overcurrent Protection Controller
Features
2.5V to 5.5V Operation
Overvoltage Protection Up to 80V
No Input Capacitor or TVS Required for Most Applications
2% Accurate 5.8V Overvoltage Threshold
10% Accurate 50mV Overcurrent Circuit Breaker
<1μs Overvoltage Turn-Off, Gentle Shutdown
Controls N-Channel MOSFET
Adjustable Power-Up dV/dt Limits Inrush Current
Reverse Voltage Protection
Power Good Output
Low Current Shutdown
Latchoff (LTC4361-1) or Auto-Retry (LTC4361-2) After Overcurrent
Available in 8-Lead ThinSOT™ and 8-Lead (2mm × 2mm) DFN Packages
Best Answer
What you show is fine. However, the diode needs to be able to handle the large current from the time the power supply is connected backwards until the fuse blows. That could be several 100 ms. Check the fuse datasheet. Usually you would use a beefy diode, not a zener. There are such things as power zeners, but if you're only trying to protect against reverse polarity and not overvoltage, you don't need the zener function. Just get a power diode.
Note that in the overvoltage case, the zener will dissipate much more power until the fuse blows than in the reverse voltage case when it's acting like a ordinary diode. The zener will dissipate a lot more than the fuse, so finding one that won't melt before the fuse does will be tricky, and expensive when you do.
The fuse and reverse diode is occasionally used, but nowadays the trend is to not force the user to replace a blown fuse unless something has really broken, in which case replacing the fuse isn't going to do any good anyway. This is a cheap and effective way to protect against reverse voltage that hardly gets in the way when the voltage is applied properly. However, you have to consider whether users are going to get upset when the fuse blows.
Unless this is low voltage and every last bit of efficiency matters, you're probably better off putting the diode in series and simply blocking reverse voltage. At low voltage, use a Shottky diode to reduce the voltage drop when operating normally. Roughly at 100 V or more, use a ordinary silicon diode.