There is no way around it.
Unless you use a switching regulator, you have to get rid of that 4.5W somewhere.
You don't need a purpose built heatsink - just bolt the regulator to a bit of metal making sure you use the correct insulating kit to insulate the regulator from the metal if the the metal is part of the car, or could touch it at any time. You won't need the kit if you can keep the metal insulated from the car.
If the current is constant at 500mA, you could dissipate some of the power in a seies 8.2 or 10 ohm 5W resistor before the regulator. The regulator may then not need a heatsink, or just a little one.