Substitution failure with `std::function` and previously deduced template parameter - why?

While I understand that generally the type of the std::function parameter can't be deduced as it is a non-deduced context.

It is not a non-deduced context. Quite the contrary. Because deduction for the parameter of std::function is attempted, but the argument is not a std::function, deduction fails. The deduction of template arguments from function arguments must agree for all function arguments. If it fails for one, it fails entirely.

[temp.deduct.type]

2 In some cases, the deduction is done using a single set of types P and A, in other cases, there will be a set of corresponding types P and A. Type deduction is done independently for each P/A pair, and the deduced template argument values are then combined. If type deduction cannot be done for any P/A pair, or if for any pair the deduction leads to more than one possible set of deduced values, or if different pairs yield different deduced values, or if any template argument remains neither deduced nor explicitly specified, template argument deduction fails.

Making the type of the second function parameter into a non-deduced context is actually how one can overcome the error.

#include <functional>

template<typename T>
struct type_identity {
    using type = T;
};

template <typename> 
struct S { };

void g(S<int> ) {}

template <typename T>
void f(T, typename type_identity<std::function<void(S<T>)>>::type) {}

int main() {
    f(0, g);
}

T is deduced successfully from the first function argument, and there is nothing left to deduce. So the dedcution is deemed a success.

Live

While I understand that generally the type of the std::function parameter can't be deduced as it is a non-deduced context, in this case T can first be deduced by the passed argument 0.

This is not true. T is deduceable in this context. If you change the code to

template <typename T>
void f(std::function<void(S<T>)>);

int main()
{
    f(std::function<void(S<int>)>(g));
}

the code would compile and T is correctly deduced.

Your issue is that you are passing an object to the function that it can't extract T from. The compiler will not do any conversion of the function arguments when it tries to deduce T. That means you have a int and a function as the types passed to the function. It gets int from 0, then tries to get the type from the std::function you pass in the second parameter but since you didn't pass a std::function it can't extract T and because of that, you get an error.