I ran into this problem where I wanted to generate balanced trees for test cases, and I decided to crack it with math.

Let X = the number of remaining open parenthesis required to reach your target length, and Y = the number of remaining close parenthesis.

Let P(X) = X/(X+Y) * (1 + 1/(Y-X+1)). Generate an open parenthesis with probability P(X), and otherwise a close parenthesis.

This will efficiently generate an unbiased random plane tree. The reason this works has to do with counting the valid ways to complete the plane tree, using a calculation similar to the one in the article.