I would hire a car and driver - your hotel / guesthouse should be able to recommend someone - and leave VERY early (like 4 AM). The road is very good on the first stretch (Livingstone to Zimba or so), so that can be done pretty safely in the dark. The sun should be coming up before you hit Choma.
Make sure to meet the driver and take a look at the car 1-2 days before so that you can change your mind / ask for a new driver / car if you don't like what you see.