Big Bend is perfect in December and January. There will probably be enough water for a decent paddle, but it potentially could be very, very low. The river actually dried up recently; you could walk to Mexico without getting your feet wet. The free permits are issued on a first come, first served basis. You will not have any problem obtaining one.
There are three canyons in the park that can be paddled. There is also the Lower Canyons section, which lies outside of the park, but is still administered by the Park Service. The run through the Lower Canyons will be more remote than anything in the park.
You will not want to use the 4x4 roads in the park as access points if that means leaving a vehicle there. Theft is a real concern. Although since the unofficial (and technically illegal) border crossings in the park have been closed, the small Mexican villages have been choked almost completely out of existence. This means most of the thieves left with the rest of the towns' populations. Still, watch where your cars are.
Lastly, and seriously, if you meet a fat, pasty Mexican (such a thing exists) on the riverbank who introduces himself as Hector, and he offers you peyote and a candelilla walking stick - buy the stick, but don't waste your dinero on his bunk cacti.