Since the power grid emergency plan with black start and system restoration scheme being the core, which is usually very complicate, is always the most critical measure for power companies to cope with the large-scale power grid outage, and thus its effective modeling and fast solving algorithm have been the challenging issue. To focus on the issue, this paper proposes a two-stage robust optimization model and a fast solving new method for system recovery considering the uncertainty of new energy power output (NEPO). Firstly, a two-stage robust optimization model that considers the uncertainty of NEPO and the constraints of AC power flow is constructed. Then, the low nonlinear transformation of power flow equation combined with second-order cone relaxation technique is proposed to transform the mixed integer nonlinear optimization model into the mixed integer second-order cone optimization model. Finally, the column and constraint generation algorithm is used to solve the problem. The effectiveness and advancement of the proposed model and algorithm are verified by a numerical example.