Using several 78xx in parallel would not be my first choice. Yes, each unit is rated at up to one amp of current and three of them could theoretically handle the load, but in practice there are slight variations in the 78xx output voltages, and since electricity prefers to follow the path of least resistance that means a circuit like the one you suggested would shunt more current through the more permissive regulator and overheat it.
My thinking was to use three switching transistors with matching resistors to shunt power around one or two big (10w) ceramic resistors, passing all current through both resistors at 12.6 volts and above, around one low-value resistor at 11.5 to 12.6 volts, around one high-value resistor at 11.0-11.5 volts. Below 11.0 volts the third transistor would pass pass power directly to the fan.
By doing the voltage reduction in a pair of robust, high-watt ceramic resistors I'd be passing the current handling and regulation tasks to components designed to handle a high-current connection as well as high-resistance heat loss. This part of the approach is very similar to what I've done to our Fantastic Fan, which has a 10-Ohm, 10-watt resistor circuit added to it to create a very slow & quiet fan speed setting.
As for a timer that would allow the fan to come up to speed, a fourth transistor/capacitor pair could shunt power directly to the fan until the capacitor reached full charge and its voltage rose to match that of the battery