Python 3.8 (pre-release), 560 bytes

I think this is correct.

Admittedly, I was much more interested in figuring out an algorithm than the golfing bit, with emanresu A significantly golfing down my initial solution. This solution does not include the \$0^n\$ string.

from random import* c=lambda d:d and c(d[1:])*len(d)/d.count(d[0])or 1 g=lambda l,x:x and[v:=l[(i:=int(x/(p:=c(l)/len(l))))]]+g(l[:i]+l[i+1:],x-l.index(v)*p)or l f=lambda n,i=1:n//i and[l+[i]for l in f(n-i,i)]+f(n,i+1)or[[]][n:] v=[(1,0,[b:=int(input())])] for p in f(b)[:-1]: x=len(p);y=x//2;z=p[y:];w=p[:y] if p[y]-w[-1]:v+=[(0,z,w)]+-~x%2*[(1,z,w)] if x%2and p[y]-z[1]:v+=[(1,z[1:],p[:y+1])] s=randrange(sum(c(B)*c(C)for A,B,C in v)) for A,B,C in v: D=c(B);E=D*c(C) if s<E: e=g(B,s%D);h=g(C,s//D) while[print(end=str(A)*[e,h][A].pop())]:A=1-A s-=E 

Try it online!

Credits for my initial solution (with sampling code): Partition code from an answer by xnor and permutation counting & indexing code adapted from this SO answer by Bartosz Marcinkowski.

Algorithm

1. For given \$n\$, we generate all integer partitions of \$n\$. The number of partitions is on the order of \$O\left(e^{\pi\sqrt{2n/3}}/n\right)\$ which crucially makes it sub-exponential for some (all?) definitions I saw (specifically one requiring any exponent to be \$o\left(n\right)\$, note the little-o). Each entry in a partition (part in mathematical terminology) represents the length of a run of zeroes or ones (the exponents in the challenge description). Note the partition function returns the parts in descending order. There's also a point of uncertainty here in that while the number of partitions is sub-exponential, I'm not 100% the specific function used to generate them is also sub-exponential.
2. Note that due to alternation of runs, there will either be equal numbers of runs consisting of ones as runs of zeroes, or a discrepancy of 1. So we iterate through each partition checking the halfway point (it ends up being finicky dealing with even/odd number of parts). Because the parts are ordered, we just need to ensure that the parts on either side of the halfway point do not equal for it to be a valid partition for this problem. The left-half will be runs of ones, the right-half runs of zeroes (for odd number of parts, taking into account whether the string as a whole would start with 0 or 1).
3. We maintain a list of 3-tuples in the following structure: (starting character, zero runs half-partition, one runs half-partition). So each valid even sized partition generates two entries in the list of tuples I'm maintaining, while odd sized partitions may have one or two entries. This allows us to loop through to calculate the total number of strings as well as the number of strings per partition/starting-character pair so that we can properly weight the selection of a random sample.
4. On randomly sampling a partition/starting-character pair, we still need to randomly select permutations of the runs. We cannot generate them as this would be factorial complexity. Luckily, permutations can be indexed in \$O\left(n^2\right)\$ time.

Complexity

Note: This describes my own calculation of the theoretical complexity of the idealized algorithm. There may remain errors in my calculation, and for code golf reasons there may be inefficiencies. Realistically, the only thing in the implementation that might push it exponential would be a sub-optimal partitions function.

The algorithmic complexity is dominated by calculating the number of permutations of the parts for each partition. Note that indexing a permutation occurs only once a partition is sampled and does not contribute to overall complexity (it's additive, not multiplicative). The average size of a partition is \$O(\sqrt{n}\log{n})\$, and per my shaky understading of this paper, that is broken down as an average of \$\sqrt{n}\$ distinct parts with \$\log n\$ duplicates. Calculating a partition's number of permutations is generally done by calculating total number (the dominating complexity), then dividing out duplicates, resulting in:

\begin{align} O(factorial\left(\sqrt{n}\log n)\right) + \sqrt{n} factorial\left(\log{n}\right)) \end{align}

Now if we take multiplication to be \$O\left(1\right)\$, factorial has linear complexity resulting in this being \$O\left(\sqrt{n}\log{n}\right)\$ and the algorithm as a whole being \$O\left(e^{\pi\sqrt{2n/3}}\log{n}\,/\sqrt{n}\right)\$. With multiplication complexity taken into account, the best known factorial algorithm is \$O\left(m\log^2{m}\right)\$. This results in \$O\left(\sqrt{n}\log^3{n}\right)\$ and the algorithm as a whole being:

\begin{align} O\left(e^{\pi\sqrt{2n/3}}\log^3{n}\,/\sqrt{n}\right) \end{align}

JavaScript (Node.js), 259 bytes

f=(n,M,c,R)=>eval(`D=n;E=M;for(C=m=0;m++<n;)for(A={},i=M-m?f:0;i<n;++i)for(d of'01')for(j=0;j++<n;i+j==n&c!=w&e&&q/(C+=q)>Math.random()&&(D=j,E=m))A[s=[i+j,w=j<m,e=d|j==m|R]]=(A[s]||0)+(q=i?A[[i,!w,d]]||0:!+d);n?(+!(D<E)+'').repeat(D)+f(n-D,E,D<E,R|E==D):''`) 

Try it online!

-1B emanresu A

Should be polynomial time by dynamic programming on (minimum 1 length*)(first color*, first length, minimum 1 length used) (* mean may be fixed because of previous decisions)