Can all permutations of a set or string be generated in O(n log n) time?
You have misinterpreted the SO question itself (or we have misinterpreted yours, which seems more likely). That SO quesiton is talking about generating a 'next' permutation from a previous given one, so that all permutations can be generated by calling 'next' multiple times. 

The answer to that is talking about the (amortized) time complexity of the C++ implementation std::next_permutation which I believe uses Narayana Pandita's algorithm, and generates them in lexicographic order.

(Also, as an aside: permutations are different from combinations. There are $n!$ permutations, but $2^n$ combinations (subsets). You seem to be under the impression that permutation is same as a combination (based on your claim of $O(2^n)$)).

To get back to the original question, another way to look at the question: would using next_permutation to generate all the $n!$ permutations in lexicographic order be $\Theta(n!)$ or $\Theta(n\times n!)$?

While there are some wrong statements in the answer you linked, it does state the right answer: It is $\Theta(n!)$, i.e. the amortized time complexity of next_permutation is indeed $O(1)$.

This can be proven as follows:

If $T(n)$ is the time taken to generate all the $n!$ permutations using next_permutation then we have that

$$T(n) = n T(n-1) + O(n^2)$$

(You fix the first number $n$ times and generate the permutations for the rest, and pay $O(n)$ cost when the first number is switched.)

Let $G(n) = \dfrac{T(n)}{n!}$. Note that we are looking the the asymptotics of $G(n)$. We get

$$G(n) \le G(n-1) + \frac{cn^2}{n!}$$

This is a simple telescoping sum, and since $\sum_{n=1}^{\infty} \frac{n^2}{n!}$ is convergent, we get that

$$G(n) = O(1)$$

Note that you could have changed the recursion to 

$$T(n) = nT(n-1) + O(n^k)$$

and still have gotten $O(1)$ amortized per permutation.