Usually that minimum current is fairly small, a few mA, you could have just an LED to tell the thing is powered up.
I would first guess what your maximum current is, I assume not more than 100 mA, so you can choose a linear regulator with those ratings:
Vin > 12V, Vout 3V3 or 5V, Iout >= 100mA
An additional note on power: for 12V in, 3V out you will dissipate 0,9W at 100 mA. That's relatively a lot, the smallest packages (SOT-23) may not cope with that, check the ones in DPAK, etc. Also, for your PCB, keep a decent copper area and vias to ground plane for heat sinking.
Alternatively, the cooler although pricier way is to have a switching regulator. You can get 90% efficiency but will have to design it, put more components, etc.