Permutation usually refers to something else, so it's probably better to call your problem "random binary words" or something similar.
The question of how long it takes to get at least one representative of each type is called the Coupon Collector Problem. If you assume that all binary words of length $N$ are equally likely, then there are $2^N$ types of coupons. You can write the time to collect all coupons as a sum of the times to collect the $i$th new coupon, a sum of independent geometric random variables. So, the expected number of coupons it takes to collect them all is $2^N \sum_{i=1}^{2^N} 1/i \sim 2^N \log 2^N$, or more precisely $2^N \log 2^N + 2^N \gamma + 1/2 + o(1)$. For $N=10$ this is about $7689$. The variance is $2^{2N} \sum_{i=1}^{2^N} 1/i^2 \approx 2^{2N} \frac {\pi^2}{6}$, so the standard deviation is about $2^N \frac{\pi}{\sqrt{6}}$. For $N=10$ this is about $1313$. Note that a normal approximation is NOT appropriate here.
One crude bound is Chebyshev's inequality, which says that the chance that a random variable is more than $k$ standard deviations away from the mean is at most $1/k^2$, and the similar Cantelli's inequality is that the chance that a random variable is at least $k$ standard deviations above the mean is at most $1/(k^2+1)$. This gives you an upper bound of about $7689 + 1313 \approx 9002$ for the median, and $7689 + 1313\sqrt{19} \sim 13412$ for the $95$th percentile.
If these bounds are not good enough, there are more precise but more complicated asymptotics known. Another approach, suitable perhaps up to $N = 25$, is to compute the exact distribution numerically using the representation as a sum of independent geometric distributions.
