Is the equation dU= TdS - PdV always valid (even for irreversible processes?)
The differential statement of the first law, $$\mathrm{d}U = T\mathrm{d}S - p\mathrm{d}V,$$ is valid for all states---but not all processes---for the reasons you have described. When we apply it, we are always assuming that a reversible process connects the two states of interest; irreversible processes are outside the range of applicability of this equation. States and processes get muddled up a lot, because we can always find a reversible process that connects any two states.

The generalization of this equation for all processes is given by $$\mathrm{d}U = \delta q + \delta w,$$ which is just the statement of energy conservation. We cannot, however, write $$\mathrm{d}U \leq T\mathrm{d}S - p\mathrm{d}V,$$ for this would imply that $T$ and $p$ are defined for a system at all points during an irreversible process, which is not true.