I've never tried dividing clematis because they say (you know, "they"

) that it is rather risky -- can easily kill the plant outright. I believe layering is considered the better means to propagate most clematis. (I've done it with C. tangutica myself, but never tried it with 'real' clematis). I also have it rattling around in the back of my head that some types come relatively easily from appropriately-timed cuttings as well...?
If you're going to try division, I'd wait til you barely see the first little green noses of new growth (which depending where you live, might mean next spring), dig it up generously, with as large a rootball as you can handle, and be very very gentle with it. See if you can ferret out a place where it 'naturally wants to' divide. (If you can't already see from aboveground a good separation between two sets of stems coming up from the roots, I wouldn't even TRY dividing it). Carefully tease it apart, preserving as many intact roots on both portions as possible. And be real, REAL nice to both halves for the next year or two.
Personally, though, I would just cut it back to the size I wanted; or, given that Nellie Moser is not the most petite clematis when happy, risk moving the entire thing somewhere else where it has suitable growing room and replant something with an intrinsically smaller habit on the trellis. If you move it, again do it when the first little green noses are just starting to show, and dig it up with as much rootball as you can handle. Moving clematis is not entirely risk-free -- if nothing else, they generally sulk for a year or even two -- but I think your chances of walking away with a living plant are higher
Good luck,
Pat