What do you do in regression if $(X^\text{T} X)^{-1}$ does not exist? Assume we want to solve $X z=b$ for $z$ where $X$ is a non-square matrix and $z$ and $b$ are column vectors. In case the system is overdetermined, we have no solution and can look  for a solution which minimizes $||Xz-b||^2$. The solution is given by the pseudoinverse, so that $z^*=(X^T X)^{-1}X^Tb$.
My question is, what happens if $X^TX$ is not invertible? In a typical regression problem, where $X$ is the matrix with features on the columns and data points on the rows. Does the problem of $X^TX$ not being invertible ever occur in regression? If so, how is it solved?

There are two common settings where the problem occurs in regression, and these are treated differently.
The first is when the number of columns $p$ of $X$ is greater than the number of rows $n$. In that case you can't do the regression, and you need some sort of dimension-reduction approach.  You might do subset selection or $L_1$-type penalisation (lasso) or shrinkage without dropping variables (ridge regression, mixed models) or just think about variables you are willing to drop.
The second is when you have just set up $X$ wrong and the solution is to fix it.  For example, if you have a $k$-level categorical variable and you set up $k$ indicator variables ('one-hot' encoding) then $X^TX$ will be singular and the solution is to change to an encoding by $k-1$ variables (just drop a variable to get treatment contrasts or switch to sum-to-zero contrasts or Helmert or whatever)
When $p$ is slightly less than $n$ and the data aren't recorded to very high precision, it's not that unusual to get get $X^TX$ singular, and that's basically like the $p>n$ setting.
It's fairly unusual to have $X^TX$ singular when $p\ll n$ and there isn't a simple and fixable symbolic issue with encoding. It's not impossible; it can happen; but it's unusual. It happened more a bit often in the Bad Old Days when we were all working with stone axes and 7-digit floating point.
