Typically Variational Inference relies on taking gradient steps on KL divergence between the variational and true posterior, or on the ELBO. This does not seem valid when variational parameters are discrete (since gradients wrt those arguments are not defined). How can we perform VI on discrete variational parameters?
Well, in general this is an instance of a discrete optimization problem, and in general there are no methods more efficient than brute-force search over all possible values of these parameters. In some special cases though, one might use problem's structure to be much better. This is studied by the field of Combinatorial Optimization. In some cases when efficient exact solutions are unknown, there exist good approximate ones.
There are practical heuristics such as Evolutionary algorithms which are not guaranteed to be better than an exhaustive search, but might lead to a decent solution (in a short amount of time).
However, design of a variational approximation in VI is arbitrary, and it makes sense to choose its family so as to make the optimization process efficient and tractable. In practice, variational approximations are almost always parametrized by continuous parameters and thus allow gradient-based optimization.