@TheoL I'm far from being an expert, so you may want to get someone else's opinion on it, but to me it looks good. Supports sufficiently high input voltages, good efficiency, and it seems to already have all the capacitors and everything, so you can get rid of all of that in your circuit.

Still, even if it was 500mA at 3V (1.5W) instead of 500mA at 12V (6W) (getting rid of all the voltage regulation losses), that would still be around 10 times what I would expect. So something strange is going on.

The LM2575T-3.3 seems to fit and costs around 50 cents on AliExpress. According to the datasheet (http://www.mouser.com/ds/2/308/LM2575-D-88310.pdf) you can have input voltages up to 45V. Efficiency might not be the best, but definitely better than a linear regulator.

This is just what I came up with when looking for switching 3.3v regulators, I don't have any actual experience with it.

And as @AWI said, your circuit really should be using very little power. From your description, you are burning 500mA@12V = 6W which is absolutely huge. That's a lot of heat to dissipate. Normal consumption for an Arduino when active (without doing anything to lower it, such as using sleep states) is around 25mA@5V = 0.125W and likely quite a bit less for a 3.3V Pro Mini. Even counting some consumption for your sensors you are at around 50 to 100 times the normal consumption (which you all have to dissipate through your heat sinks).

I'm not an expert, but your voltage regulation seems strange to me.

Apparently you are using two linear regulators to first drop from 12V to 8V (originally 5V), and then from there to 3.3V. This means that you are burning almost 75% of your power in those regulator, which ends up as heat you need to dissipate. Just use a switched regulator instead and you get rid of all those problems.

This might also explain why your electronics use so much energy. The power used by your Arduino and sensors should be absolutely negligible compared to the LEDs, so you really shouldn't need to account for that when choosing the power supply. If you do, then your power supply is far too weak to drive the LEDs reliably anyway.