Don't use the 12V\$\rightarrow\$5V regulator, the Arduino needs at least 7V in. Use the battery's 12V directly instead.
The capacitor's value will depend on the Arduino's power consumption. The Arduino webpage doesn't say what the Uno consumes, so you can't say right away what capacitor value it needs. In any case it's not designed for low power. I checked the datasheet for the voltage regulator, and that alone already uses 6mA. On the schematic I can see two microntrollers: an ATMega16U2 running at 16MHz, and an AtMega328P, also at 16MHz. The former may consume up to 21mA, the latter says 9mA at 8MHz, so it's safe to say 18mA at 16MHz. We already have 45mA, let's round it to 50mA for the other components.
If a capacitor is discharged at a constant current, then
\$ \Delta V = \dfrac{I \cdot t}{C} \$
You start at 12V, and the Arduino needs a minimum of 7V, so \$\Delta V\$ = 5V, I was 50mA and t = 3s. Then
\$ C = \dfrac{I \cdot t}{\Delta V} = \dfrac{50mA \cdot 3s}{5V} = 30 000\mu F \$
That's the minimum, I would pick a 47 000\$\mu\$F/25V capacitor. Add detection for power off, so that you can switch off all unnecessary outputs which also may consume current, a relay for instance.
If you want to know exact what the power consumption is, add a 1\$\Omega\$ resistor in series with the power supply and measure the voltage drop. A 50mV drop means 50mA consumption.
Also add a TVS (Transient Voltage Suppressor) at the Arduino's power input; a car's 12V is extremely dirty.
Add the diode clabacchio mentions. A series resistor of 10\$\Omega\$/5W will charge the capacitor in 1.5s when applying power.
Yes, it can be done, with due care.
The laptop battery described could typically provide quite a few jump starts. Getting it to do so safely and effectively is "the trick". Read on ...
What is often not generally appreciated is that energy to turn the starter motor during a jump start does NOT come directly from jump-battery to starter but is first transferred from jump-battery to car-battery and then from car-battery to starter motor. (See note at end)
The starter motor draws hundreds of amps - probably 100-200 Amps in a very good situation and 400-600-800 Amps in various other cases. Even when the car-battery has been run flat by lights left on or whatever, it has the ability to accept energy from the external source and then to return it to the starter motor.
A 11.1 V LiIon battery probably has 3 cells in series.
11.1/3 = 3.7V/cell. Actual cell voltages will be about 4.2V fully charged and 3V dead dead, so the battery = 9V to 12.6V. It is OK to use down to about 9.3V. At 9V if it does actually charge you are in the area where it is doing damage to the battery to use it.
Issues are
If car battery is very flat its terminal voltage may be low enough that the laptop-battery provides more current than is wise. The laptop-battery can be damaged and lose cycle capacity and worst case can "vent with flame" - spectacular high energy melt down.
If the car battery is very high impedance due to eg major internal sulphation the voltage may be around 12V when open circuit. The laptop battery open circuit voltage may be lower than the car-battery voltage and no energy transfer may occur. This will probably not usually be what happens.
If the laptop battery was rather flat (around 9V) and the car battery had modest life in it (eg starter relay goes click-click-click but starter will not turn, headlights light dimly) then the car-battery voltage may be usefully greater than the laptop-battery voltage and the charging may occur in the opposite direction. Max safe charging voltage for your laptop battery is probably about 8.4A (A = Ah rate). A battery that may not start a car may happily deliver 10 x as much current as the laptop battery can safely handle.
"Vent with flames" / fireball / pyrotechnics may well eventuate. you'd be needing a new laptop battery. The car battery would not have noticed.
In many cases you may be able to 'just connect the batteries " +ve to +ve, -ve to -ve and get an acceptable result. But, as above, maybe not.
Adding a series diode of suitable current rating will protect against charging the laptop battery. You can still get excessive current the other way. And voltage available is reduced.
The laptop battery would be good for this purpose if properly used.
What is needed is some limit on safe maximum current, and a voltage for charging that is suited to the car battery in any state. You could make such but you can but them on ebay for less than you can make them for - or from China for perhaps slightly less again.
What you need is a power supply with Vin is at least 9V - 13V, Vout is say 13V-14V and current out is limited to say 5A. If the car battery loads down the supply then the current limit should work. such supplies probably cost in the $US5-10 range on ebay. You can pay more.
Note: You will find much discussion on whether jumpstart energy is first saved in the car battery. I'm wholly convinced that it is. I have started cars from battery packs joined with twisted connections and thin wire and connected to the battery by 3 feet + of "lamp cord.
Eureka! Very satisfying when it works. A starter motor would not even notice that such a battery was there.
If you have REALLY heavy jump start leads, big solid connecting clips and some luck then you may be able to jump start directly from the remote battery. I've seen it done once when all normal attempts failed. The AA was called and he had a monster battery and lead set. It only just worked and his leads nearly melted. It charged and ran OK after that and I have no idea why it behaved that way. ALL the jumps start packs sold have no chance of starting a car directly.
Best Answer
When cranking a car engine, the battery voltage sags significantly. Real automotive electronics is designed and tested against these special brown-out conditions. One solution to this problem (except it was a bluetooth device) is given here.
The solution includes a super capacitor (100 mF) and a Schottky diode, to prevent possible back flow discharge.
While technically the diode-capactior network should be placed at 12V side (it would require less capacitance to hold the same amount of charge), the cost of 16-V supercaps is much higher (`20X) than 5-V supercups.
The other solution would be a 5-V circuit with battery backup with hold time of 20-30 seconds. It will have smaller size (a 50 - 100 mAh Li-ion battery would be enough), but electronics will be much more sophisticated and expensive.