Wait, ignoring firmware... you need to have some charge in order to charge with USB-C? Couldn't it use the lowest power modes until it has enough juice to communicate? This seems like a serious flaw with USB PD.
Just to be pedantic, USB-C does need negotiation before it provides 5V, but that negotiation is just a pair of resistors of a specific value.
(Since the USB-C cable is symmetric, this negotiation is necessary to decide which end will provide the power. One end has both resistors wired as a pull-down, and the other end has both resistors wired as a pull-up. The end with both resistors wired as a pull-up will initially provide the 5V power.)