Black-box combinatorial optimization problem over permutations
In general if you know nothing about f and it can be totally arbitrary, then there is nothing you can do: you cannot do better than brute-force.  If f has no structure, no properties, no regularities, and is just totally random, then it is easy to see that any algorithm has to compute f on all $N!$ possible permutations to find the minimum.

In practice it is common to deal with functions f that do have some degree of structure.  For instance, if x,x' are similar (for some notion of similarity), then f(x),f(x') might have a good chance of being similar.  In those cases you can use techniques like local search.  But if you don't have that property, then you can't use local search, and you may be back to a situation where you cannot do any better than brute force.

There are other approaches in other situations: e.g., if we know the symbolic expression for f, we might be able to use a SAT solver, especially if that symbolic expression is not too large.  But again this requires f to have some structure and not be totally arbitrary.

There are no silver bullets.  You need to know something about f to have a hope of doing anything.