It's not about not being able to compute something.
Distances much be used to measure something meaningful. This will fail much earlier with categorial data. If it ever works with more than one variable, that is...
If you have the attributes shoe size and body mass, Euclidean distance doesn't make much sense either. It's good when x,y,z are distances. Then Euclidean distance is the line of sight distance between the points.
Now if you dummy-encode variables, what meaning does this yield?
Plus, Euclidean distance doesn't make sense when your data is discrete.
If there only exist integer x and y values, Euclidean distance will still yield non-integer distances. They don't map back to the data. Similarly, for dummy-encoded variables, the distance will not map back to a quantity of dummy variables...
When you then plan to use e.g. k-means clustering, it isn't just about distances, but about computing the mean. But there is no reasonable mean on dummy-encoded variables, is there?
Finally, there is the curse of dimensionality. Euclidean distance is known to degrade when you increase the number of variables. Adding dummy-encoded variables means you lose distance contrast quite fast. Everything is as similar as everything else, because a single dummy variable can make all the difference.
K-means does not use a distance matrix.
The method requires a data matrix, because it computes the mean. It nowhere uses pairwise distances, but only "point to mean" distances. The mean is a good choice for squared Euclidean distance. It's not particularly good for regular Euclidean. It's only defined for continuous variables. So it cannot be used with Gower's on categoricial data.
If you have a distance matrix (and little enough data to store it), then hierarchical clustering is likely the method of choice.
Yes, it probably is a good idea to use non-metric multidimensional scaling (MDS) and tSNE to check if the distance function works on your data. There is no guarantee that a distance gives useful results. If these visualization just give you a random-like blob, then do not expect the data to cluster with this distance.
Best Answer
K-means can only be used in data sets where you can compute the arithmetic mean.
Use hierarchical clustering instead. It can use distance matrixes, including Gower distances.