Idea for Noise Level Estimation / Automatic Thresholding in the Presence of Peaks
I'd do some small adjustments to your idea (You really nailed them).

Assumptions


The Signal Model - Signal + Additive White Gaussian Noise (AWGN)
Probably we could generalize it more but this is beyond the scope of this question.
The DFT of the signal contains Peaks with relatively small roll off
This is important as we're almost saying the Signal is a combination of sparse number of Harmonic signals. As the lobes width will hide the noise data. So the ratio between the observation window, signal lobes width and sampling rate means that the DFT of the data creates sharp peaks.


Estimation

Under the above assumptions we know that:


Noise is AWGN in the DFT (As Gaussian Vector stays Gaussian under linear transformations). It also suggests that the Mean Value and the Median are similar (Realization of Symmetric Distribution).
Without the Signal Data the Mean and the Median value of the beans should be similar.
Number of bins contaminated with signal (Funny to write this, ha?) is sparse.


So we can sort the bins, but sorting and evaluating the mean on sub set will create bias unless we make sure the sub set is symmetric around the Mean / Median.
So, I'd sort the data and keep bins in the 25-75 Percentile range only. I'd use Mean on those.