Все будет зависеть от параметров шума. Например, если энергия шума сосредоточена в узкой полосе, то Вам прийдется отличать один узкополосный сигнал от другого.

Если же шум можно принять аддитивным белым гауссовым, а сигнал - синусоидой, то наилучшим решением наверняка будет сначала грубое определение частоты синусоиды(например, поиск тона с максимальной энергией в преобразовании Фурье) в качестве начального приближения и затем методами нелинейной оптимизации поиск частоты, амплитуды и фазы синусоиды, после вычитания которой из сигнала остаток будет иметь минимальную энергию. Да, если частота изменяется медленно - преобразование Фурье можно считать один раз, а для последующих секунд в качестве начального приближения брать результат предыдущей секунды.

Да, если в сигнале много гармоник основного тона - ситуация может осложниться.

Но вообще говоря, так как задача нелинейная, многое зависит от Вашего сигнала, шума и мощности процессора. Можно придумать много методов, различающихся требованием к ресурсам и надежностью получаемых результатов. Например, как промежуточное решение, в преобразовании Фурье выделяете главный тон, потом берете его наибольшего соседа и по отношению их энергий таблично находите правильное положение пика между этими тонами. Или вычислянте фазу синосоиды с частотой главнго тона в преобразовании Фурье отдельно для двух половинок, смотрите, на сколько ушла фаза за полсекунды, и прибавляете поправку к частоте этого тона. Какая при этом получится точность я Вам с ходу не скажу, можно либо оценивать, либо определять экспериментально.