I am deciding if I will travel to Kyoto in late November, early December.
- How cold is the weather?
- Is there still a chance to appreciate the fall's splendid colors or will trees have lost all their leaves by then?
Using the Wikipedia weather history of Kyoto and the current weather forecast (as of mid-november 2013), one can figure that between mid-November and mid-December one could expect temperature between 5 and 20°C (low and high of each day), with possible extremes of 0 to 25°C. This is pretty imprecise since it could vary every year, but in 2013 this seems quite accurate.
As of your second question, i.e. whether the trees would have lost their leaves already, while I have never been to Kyoto, I ran a search on the photography website Flickr with date restriction between November and December 2012 (I get similar results for 2010 to 2013) and it shows a lot of pictures taken around that time with trees full of leaves (indeed that's pretty nice, by the way). So you should probably be able to see some nice trees while you are there.
See Wikipedia for average weather stats: