Optimizing FFT code for 12 bit processing on microcontroller
12-bit is not a native data type on your platform, so the best you can do without loss of precision is 16-bit per sample, in Q15 format.

I don't know the Stellaris line well, but from what I gathered on the TI website, these are either Cortex M3 (LM3xxx) or Cortex M4 (LM4xxx).

The Cortex M4 embeds a floating point unit; so there won't be as much benefit in terms of run-time from converting your code to fixed point as you think. The immediate thing is to switch to 32-bit floats. The next thing is to check your compiler settings and have a quick look at the disassembled generated code to check that it actually generates floating point instructions rather than using emulation. With gcc, you'll probably have to use compilation flags like -mcpu=cortex-m4 -mfloat-abi=hard -mfpu=fpv4-sp-d16 (which are the flags I use with another Cortex-M4 product). There's a good chance you'll get better performance from using a vendor-supplied function rather than your own code. Try arm_cfft_radix4_f32 in the CMSIS DSP library. This should solve your performance problems.

If you use a M3 part instead, and/or are really short on RAM for your samples, you'll have to switch to fixed point (Q15 format). Again, you don't have to write code for that, just grab the CMSIS DSP library provided by TI and use the functions arm_rfft_q15 (for real input) or arm_cfft_radix4_q15 (for complex input, if the input size is a power of 4).