With categorical data, can there be clusters without the variables being related? When trying to explain cluster analyses, it is common for people to misunderstand the process as being related to whether the variables are correlated.  One way to get people past that confusion is a plot like this:

This clearly displays the difference between the question of whether there are clusters and the question of whether the variables are related.  However, this only illustrates the distinction for continuous data.  I'm having trouble thinking of an analog with categorical data:
ID  property.A  property.B
1   yes         yes
2   yes         yes
3   yes         yes
4   yes         yes
5   no          no
6   no          no
7   no          no
8   no          no

We can see that there are two clear clusters: people with both property A and B, and those with neither.  However, if we look at the variables (e.g., with a chi-squared test), they are clearly related:
tab
#      B
# A     yes no
#   yes   4  0
#   no    0  4
chisq.test(tab)
# X-squared = 4.5, df = 1, p-value = 0.03389

I find I am at a loss for how to construct an example with categorical data that is analogous to the one with continuous data above.  Is it even possible to have clusters in purely categorical data without the variables being related as well?  What if the variables have more than two levels, or as you have larger numbers of variables?  If the clustering of observations does necessarily entail relationships between the variables and vice versa, does that imply that clustering is not really worth doing when you only have categorical data (i.e., should you just analyze the variables instead)?

Update: I left a lot out of the original question because I wanted to just focus on the idea that a simple example could be created that would be immediately intuitive even to someone who was largely unfamiliar with cluster analyses.  However, I recognize that a lot of clustering is contingent on choices of distances and algorithms, etc.  It may help if I specify more.
I recognize that Pearson's correlation is really only appropriate for continuous data.  For the categorical data, we could think of a chi-squared test (for a two-way contingency table) or a log-linear model (for multi-way contingency tables) as a way to assess the independence of the categorical variables.
For an algorithm, we could imagine using k-medoids / PAM, which can be applied to both the continuous situation and the categorical data.  (Note that, part of the intention behind the continuous example is that any reasonable clustering algorithm should be able to detect those clusters, and if not, a more extreme example should be possible to construct.)
Regarding the conception of distance, I assumed Euclidean for the continuous example, because it would be the most basic for a naive viewer.  I suppose the distance that is analogous for categorical data (in that it would be the most immediately intuitive) would be simple matching.  However, I am open to discussions of other distances if that leads to a solution or just an interesting discussion.
 A: As I'm sure you know, correlation is a measure of the linear relationship between two variables, not how close the points are to each other. This explains the top four figures.
Of course, you could also create similar graphs for discrete, real-valued data as well.
The problem with more abstract distributions, such as $X \in \{A,B,C,D\}$ is that, unlike variables taking values in $\mathbb{R}$, we cannot assume that the image of a categorical random variable forms a metric space. We get this automatically when $X \subset \mathbb{R}$, but not so when we have $X$ taking values on some arbitrary set. 
You'd need to define a metric for the categorical space before you can really even talk about clustering in the geometric sense.
A: @ttnphns' point about pairwise vs multivariate association is well taken. Related to that is the old saw about the importance of demonstrating association with simple metrics before leaping into a multivariate framework. In other words, if simple pairwise measures of association show no relationship then it becomes increasingly unlikely that multivariate relationships will show anything either. I say "increasingly unlikely" because of a reluctance to use the word "impossible." In addition, I am agnostic as to the metric employed whether it be a monotonic Spearman correlations for ordinal data, Somer's D, Kendall's Tau, polychoric correlation, the Reshef's MIC, Szelkey's distance correlation, whatever. The choice of metric is not important in this discussion.
The original work done on finding latent structure in categorical information dates back to the early 50s and Paul Lazersfeld, the Columbia sociologist. Essentially, he invented a class of latent variable models that has seen extensive development and modification since. First, with the 60s work of James Coleman, the U of C political economist, on latent voter election propensities, followed by the contributions of the late Clifford Clogg, also a sociologist, whose MELISSA software was the first publicly available latent class freeware. 
In the 80s, latent class models were extended from purely categorical information to finite mixture models with development of tools such as Latent Gold from Statistical Innovations. In addition, Bill Dillon, a marketing scientist, developed a Gauss program for fitting latent discriminant finite mixture models. The literature on this approach to fitting mixtures of categorical and continuous information is actually quite extensive. It's just not as well known outside of the fields where it has been most widely applied, e.g., marketing science where these models are used for consumer segmentation and clustering.
However, these finite mixture model approaches to latent clustering and contingency table analysis are considered old school in today's world of massive data. The state-of-the-art in finding association among a huge set of contingency tables are the decompositions available from deploying tensor models such as those developed by David Dunson and other Bayesians at Duke. Here is the abstract from one of their papers as well as a link:

Contingency table analysis routinely relies on log linear models, with
  latent structure analysis providing a common alternative. Latent
  structure models lead to a low rank tensor factorization of the
  probability mass function for multivariate categorical data, while log
  linear models achieve dimensionality reduction through sparsity.
  Little is known about the relationship between these notions of
  dimensionality reduction in the two paradigms. We derive several
  results relating the support of a log-linear model to the nonnegative
  rank of the associated probability tensor. Motivated by these
  findings, we propose a new collapsed Tucker class of tensor
  decompositions, which bridge existing PARAFAC and Tucker
  decompositions, providing a more flexible framework for parsimoniously
  characterizing multivariate categorical data. Taking a Bayesian
  approach to inference, we illustrate advantages of the new
  decompositions in simulations and an application to functional
  disability data.

https://arxiv.org/pdf/1404.0396.pdf
