The diagram to the schematic shows an approach that ought to work, so you seem to be on the right track. I would probably add snubber diodes across the relay coils to prevent inductive kickback, but the ULN2803A is supposed to take care of this for you, so my addition may be a case of belt and suspenders overengineering.
A scope would certainly be helpful to track down the high pitched buzzing, but you can still do a fair bit of troubleshooting with a meter.
When you say you're using it "in a car with a regular 12V battery" I assume you mean the car's 12V lead-acid battery? That's got well more than enough current capability to drive the relays.
I'd start by disconnecting the wire connecting your arduino out to the input of the ULN2803A. Take the arduino out of the picture for a minute and connect the input of the ULN2803A directly to the +5V supply to turn the relay on, and wire it to ground to turn them off. Do the relays work now? Measure the current consumed by the ULN2803A input when the relay is turned on. The data sheet says it's got a 2.7k resistor on the input, so input current should be somewhere around 5V/2.7k, or less than 2 mA, well within the ability of the Arduino to deliver (there will be some diode drops in there, so the 2.7k input resistor shouldn't see the full 5V, so the current ought to be even less than I calculated).
If things are good so far, then connect the darlington back to the Arduino, and set the Arduino output high. Measure the voltage and current on the Arduino output pin. It should be very nearly 5V, and the current ought to be very close to the same as you measured earlier. Both voltage and current should be steady and reliable, unchanging. If you don't get good readings here, then I'd suspect a software problem is causing your Arduino outputs to not be high like they're supposed to be.
My wild unsubstantiated guess is that you've got a software issue where your Arduino pin isn't being held high, but is oscillating between high and low, and isn't staying high for long enough to switch the relay. But that could easily be wrong. You might have a bad darlington array, or the relays may be beyond the ability of the darlington array to handle. If so, that'll show up when you connect the input of the darlington array to +5V.