Is $O (N \log N)$ FFT speed the fastest we can ever attain?
While the general problem remains an open problem in theoretical computer science, there are (randomized) algorithms known as sparse fast fourier transforms which can approximate DFTs to a certain approximation factor when there are only a few DFT coefficients you are concerned with. 

You can find some details in these papers and related papers (downloadable here):


Hassanieh, Haitham, et al. "Nearly optimal sparse Fourier transform." Proceedings of the 44th symposium on Theory of Computing. ACM, 2012.
Hassanieh, Haitham, et al. "Simple and practical algorithm for sparse Fourier transform." Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2012.