I don't know if this has been programmed. I'll describe one method based on counting. Let $c_{n,m}$ be the number of labelled connected graphs with $n$ vertices and $m$ edges.

Choose a pair of distinct vertices $v,w$. By symmetry we can assume $vw$ is an edge. There are several cases:

- Case 0: $vw$ is not a bridge. The number of such graphs is
$\frac{\binom n2-m+1}{\binom n2}c_{n,m-1}$.
- Case $(k,\ell)$: $vw$ is a bridge and after removing $vw$ the component containing $v$ has $k$ vertices and $\ell$ edges, while the component containing $w$ has $n-k$ vertices and $m-\ell-1$ edges. The number of such graphs is $\binom {n-1}{k-1} c_{k,\ell} c_{n-k,m-\ell-1}$, where the $\binom {n-1}{k-1}$ is for choosing which vertices form the component that contains $v$.

Now you need to choose between these cases with probabilities proportional to the number of graphs in each case. Once you choose the case, generate the graph using one or two recursive calls to your generator. In case 0 you need a connected graph with $m-1$ edges such that $vw$ is not an edge; just generate any connected graph with $m-1$ edges, choose a random non-edge and relabel so that it is $vw$.

Note that the numbers $c_{n,m}$ can be computed by the same recurrence. Use memoisation to avoid exponential time and be prepared for very large values. Using floating point approximations to $c_{n,m}$ should give random graphs practically indistinguishable from those using exact values.