The strong Kantorovich duality, i.e. the existence of dual solutions, holds whenever $c$ is lower semicontinuous and **real-valued**, and the optimal coupling has finite cost, see Theorem 5.10(ii) in Villani "Optimal Transport old and new". In contrast, for the weak duality ("$\inf = \sup$") it suffices to assume $c$ is lower semicontinuous.

To prove 5.10(ii) one constructs an explicit $c$-concave function $\varphi$ that is finite-valued on the support of $\mu$, see formula (5.17). Beware of signs! Villani is looking at $c$-convex functions and you at $c$-concave functions.

The answer the "value part" of the question: the values of $\psi$ and $\varphi$ are only important on the suport of $\mu$ and resp. $\nu$. Everywhere else you may choose them to be $-\infty$ (loosing $c$-concavity). The standard construction shows that $\varphi$ is either constant equal to $0$ or has values $0$ and somewhere $1$ (choose a chain of length $m=1$ in (5.17). This shows that $\psi$ must have value in $\{-1,0\}$ on the support of $\nu$. By a different argument this was observed already in the question's update.

Note if $c$ is not real-valued then there may not be any dual solutions between certain measures $\mu$ and $\nu$, see the [preprint][1] of S. Suhr and me on Lorentzian cost function, more explicitely Section 3.1.


  [1]: https://arxiv.org/abs/1808.04393