Uniform sampling with constraints
If your constraints can be described using a small DFA, then you can use sampling-by-counting, which works in the following way. For each $\sigma \in \Sigma$, count the number of legal strings starting with $\sigma$ (as explained below), and use this to sample the first character, say $\sigma_1$. Then, count the number of legal strings starting with $\sigma_1 \sigma$ for all $\sigma \in \Sigma$, and use this to sample the second character; and so on.

It remains to explain how to count the number of strings of length $n$ with prefix $x$ accepted by a given DFA. Let me start with the case $x = \epsilon$. The idea is to use the transfer matrix method: construct a matrix $A$ in which $A(q_1,q_2)$ is the number of edges from $q_1$ to $q_2$ in the DFA (that is, the number of symbols $\sigma$ such that $\delta(q_1,\sigma) = q_2$). It is not hard to check that $A^n(q_1,q_2)$ is the number of words of length $n$ which carry the DFA from $q_1$ to $q_2$. Taking $q_1$ as the initial states and summing over all final states for $q_2$, we obtain the number of words of length $n$ accepted by the DFA.

Given a prefix $x$, we do exactly the same, only counting words of length $n-|x|$ that are accepted by the DFA when started at state $\delta(q_0,x)$.



As a simple example, you can use this technique to sample a word of length $2n$ over $\{a,b\}$ having an equal number of $a$ and $b$. Although the corresponding infinite language isn't regular, you can construct a DFA for this language which has $O(n)$ states, making the above approach feasible. In this particular case there are also known closed formulas for the number of words of length $n$ with prefix $x$.



With some work, you can probably extend this approach to context-free grammars. One thing to try would be to extend the CYK algorithm so that it counts the number of words of given length with a given prefix.