You are lucky because you can do this on your own schedule. When we have a new and look and feel that we want to fold into the application, we always have to do it piece-wise. This is because the application is just so huge that it is difficult to get through testing everything with a new look-and-feel in one release; and, because we did a poor job of initially separating the view from the data. I agree with other two answers that you should look at what features your users care about most of all, and tackle those first. Second, I would look at refactoring code as you go (a good principle of Agile design is to build in a certain amount of time each release into refactoring) to put more things into a view-controller like CSS. Then pushing the look-and-feel through the app.
Last, you should evaluate the purpose of the overhaul. Are you doing it for the big wow-factor? If so, branch the code and work on the look and feel for a big release. Or, are you doing it because the previous look-and-feel is creating a ton of usability problems? If so, pushing out piece-wise might make more sense.
