I've never used one, but they actually make frequency-to-voltage chips (
example). With your specific requirements, you'd probably need an op-amp circuit to calibrate & "scale" the output. (I'm just
assuming that the chip will put-out zero-volts at zero-Hz, and you'd need to compensate to get 0V@ ~6kHz, etc.)
Typically, a
frequency counter works by counting the number of cycles (or the number of positive zero-crossings, etc) over a period of time. You first need a comparator circuit to convert your AC input into nice pulses.
Then, you just need a counter circuit to count the pulses over a fixed-known period of time. So far, none of this needs a microcontroller. It's actually better if you can do the counting & timing without relying on software which might not be able to keep-up. A microcontroller would be helpful for calculating the frequency (if your time reference isn't 1 second) and for storing the result, etc.
Then, you can use a digital-to-analog convert to make an analog voltage. (Or, the PWM features of the Arduino.)