You can use the web edition to develop a Nios II system and just tether it over JTAG when you download to the board. If you were going to ship what you are working on then yes you would need to get a Nios II license.
FFT is a fairly computational algorithm so you might find writing that in C will work for the line rate you need. If I was implementing this I would probably use Nios II for the control plane and use dedicated hardware for the FFT and DMAs to move data around. Here is an example MP3 player that you can take a look at:
http://www.alterawiki.com/wiki/mp3_player