Most efficient way to extract frequency components of audio signal with near-human accuracy in real time
First, with the classic short-term Fourier transform approach, there are alternative to interpolation - in particular techniques making use of phase information to recover the instantaneous frequency (See this question) which can give you very accurately the position of a spectral peak without an increase of FFT size. The drawback, as you correctly said, is that you are not increasing the ability of the system to discriminate adjacent peaks - but this is already a great improvement compared to using the central frequency of the FFT bin index.

Regarding your brute force approach... FFT has this resolution limitation (with bins at $\frac{sr}{FFT\_size}$) because it is "probing" the signal with complex exponentials that have a null integral over the analysis window - and these must have a period which is an integer division of the length of the analysis window. If you try to naively use the same approach to "probe" frequencies at other ratios, it won't work because you'll be "probing" your signal with functions that do not contain a complete cycle. If you wanted to make it work, you would have to increase your analysis window to the least common multiple of the periods of all the signals in your brute-force search, and this is precisely what you want to avoid!

There is another brute-force approach that works: "probe" your signals with windowed complex exponential (Gabor wavelets). These are characterized by a center frequency, a center time, and a bandwidth (which measures how the wavelet is spread over time or over frequency). You'll have to evaluate many, many, many correlations between your signal and these wavelets at as many time offsets, frequencies, and bandwidths you want. The result will be the same as a very flexible "tiled" STFT in which an optimal window size is selected for each time-range and each frequency-band. Besides the computational cost, the downside is that there is no efficient algorithm, and no causal algorithm (you will need to know as many samples in advance as the longest wavelet in your dictionary). If you want to experiment with these techniques, have a look at MPTK.

A last class of approaches working quite well for music signals are subspace tracking / high resolution methods. They work the problem from a model estimation angle - "assuming this signal is a sum of $k$ exponentially damped sinusoids, what are the best amplitudes/frequencies giving the least square error?", and as such the number of samples required to get an accurate estimate is only dependent on the noise level. There are some hurdles to make them work, though:


The number of components $k$ must ideally be known in advance. Order estimation methods like ESTER have been proposed to optimally pick the model order.
They perform well in the presence of white noise - this requires the signal to be whitened before analysis; performing the analysis in individual channels of a filter bank helps too.


These are computationally expensive, but they can work online, with short windows if model orders and/or noise are low.