Как выделить шаблонность из функции?

Если единственное использование - это X x = expr; *it++ = x;, то эту операцию можно обернуть в std::function<void(X)> f, передавать не итератор а эту функцию, использовать как f(x).

Либо можно передавать класс с виртуальными функциями.

По сути, все что вам нужно это полиморфное поведение вашего итератора. Сейчас вы достигаете полиморфизма за счет шаблонов. Можно достичь того же эффекта при помощи наследования и виртуальных методов.

Для начала объявим интерфейс итератора:

class IIterator{
public:
    virtual void next() = 0;
    virtual void setValue(int value) = 0;
    virtual int value() const = 0;
    virtual ~IIterator(){}
};

Думаю вы знаете тип значения, которое хотите писать в итератор. Для примера я взял int.

Теперь нам нужна конкретная реализация, причем для всех возможных итераторов. Да, снова шаблоны:

template<class It>
class Iterator : public IIterator{
    It _iterator;
public:
    explicit Iterator(const It &iterator):
        _iterator(iterator)
    {}
    void next(){
        ++_iterator;
    }
    void setValue(int value){
        *_iterator = value;
    }
    int value() const{
        return *_iterator;
    }
};

Теперь возьмем весь код из void terribleFunction(Itor it), перенесем его в функцию void terribleFunctionHelper(IIterator &it), и внесем некоторые изменения в использование итераторов:

void terribleFunctionHelper(IIterator &it){
    //...
    it.next();         //Раньше тут было ++it;
    it.setValue(42);   //Раньше тут было *it = 42;
    //...
}

Код void terribleFunction(Itor it) теперь станет таким:

template<typename It>
void terribleFunction(It it){
    Iterator<It> iterator(it);
    terribleFunctionHelper(iterator);
}

В результате этих нехитрых манипуляций, все зависимости оказались в нешаблонной terribleFunctionHelper. Можно смело переносить ее код в cpp файл.

Полный пример