Getting advance parole is very straight forward case. You can apply for advance parole and work permit along with the the I-485 (adjustment of status). It's extra 15 mintues worth of time and a couple of hundred dollars for filing fee. However, before your wife is able to apply for adjustment of status, I think your sponsorship has to be approved (for other employment based applicants their I-140 had to be approved). Only Vermont and California accept new cases of I-130. Dhiren might have first hand experience about this, better call him. I haven't heard any cases of denial to entry for those who travel with approved advance parole document. You don't have to wait until greencard approval for travel.