Algorithm to generate inputs with certain properties, but not accepted by a given regular language
For your specific question, you are asking to generate a string in $\bar{L} \cap P$.  Note that since $L$ is regular, so is $\bar{L}$; and note that $P$ is context-free.  It is known that the intersection of a regular and context-free language is context-free.  So, you're asking: given a context-free language, how do we generate a word in that language?  This is straightforward.

Concretely: you could represent $L$ as a DFA, then take the complement to get a DFA for $\bar{L}$.  You could represent $P$ as a context-free grammar.  Then, using a product construction, you can obtain a context-free grammar for $\bar{L} \cap P$, remove all non-productive nonterminals, and then generate a random derivation in the grammar (or, if you want to get fancier, you can search for the shortest word in the grammar using a simple algorithm).

The product construction works by replacing each nonterminal $T$ from $P$ with nonterminals of the form ${}_sT_t$, with the intended meaning that $L({}_sT_t)$ is the set of all words $w \in L(T)$ such that if you start the DFA in state $s$ and then feed in $w$, it ends in state $t$.  You can figure out how to modify all the rules of the grammar, e.g., $T \to UV$ becomes the collection of rules ${}_sT_u \to {}_sU_t {}_tV_u$ for all states $s,t,u$.

You can find the shortest word in a context-free grammar by a simple iterative algorithm.  For each grammar symbol $T$, let $\ell(T)$ denote the length of the shortest word generated by $T$, i.e., the shortest word in $L(T)$; we assume $\ell(a)=1$ for all terminals.  As a notational convenience, if $\alpha=\alpha_1\cdots \alpha_k$ is a string of terminals and non-terminals, set $\ell(\alpha)=\ell(\alpha_1)+\dots+\ell(\alpha_k)$.  Initially, set $\ell(T) := \infty$ for all nonterminals $T$ and treat all rules as unmarked.  Then, repeat the following.  Pick an unmarked rule $A \to \alpha$ where $\ell(\alpha)&lt;\infty$, set $\ell(A) := \min(\ell(A), \ell(\alpha))$, and mark that rule.  Repeat until convergence.  After this is finished, $L(S)$ tells you the length of the shortest word output by the grammar, if $S$ is the start symbol of the grammar.  You can augment the algorithm to keep track of the word itself as well as its length, and then you'll be able to output the shortest word in the grammar.

This might be handy for your application, because it gives you the shortest counterexample: the shortest string that has balanced parentheses but isn't accepted by your regexp.