The ATmega328 datasheet allows a fairly wide range of clockspeeds for the A/D converter. You can always trade speed for resolution. It lists conversion times in the 13-260 microsecond range.
Analyzing the frequency will be the more difficult part. Not only do you require sufficient sampling speed but also a lot of hefty math functions. The 8 bit AVR chips may not be the best choice for that kind of application. There are micro-controller chips from TI and PIC that have special purpose DSP hardware on chip and are a better match for this kind of stuff.
Not saying it can't be done on a Arduino, but I'm sure it won't be a walk in the park getting the code to work.