Electronic – arduino – Is it safe to connect Arduino/Netduino to car voltage source

You can use a 7805, but only to power the Arduino; the LEDs should then be powered directly from the 12V supply, since the 7805 can only supply 1A. A higher current, if possible, would also require a considerable heat sink.
And that's where a switcher comes in. Since the lights can run on 12V, but also 5V, there will be huge power losses when running off a 12V supply. 30W at 5V is 6A, and 6A over (12V - 5V) is 42W wasted. The best solution would be to have a switcher that gets you the 5V for both Arduino and LEDs, and you won't get this kind of power loss. Switchers for these voltages can reach efficiencies of more than 85%, so consuming 30W will result in a loss of 5W, down from 42W.

National's Webench designer suggests a design around an LM2743 which is even 94% efficient (only 2W loss in regulator).
Linear Technology also lists several devices that can handle the job.

You don't need a separate step-down converter, if you already have a charging IC for the battery. A lot of charger ICs take input voltages of 12V and allow the load circuit to be connected in parallel to the battery. I personally would go for an IC with an 12V input and an option to charge the battery over USB. However, I don't have build such a circuit and have no experience with a specific device. A list of manufacturers had to include maxim and microchip.