H-1 to H-4 to H-1

First H-1B filed with company A in 2011.Left Company A in February 2014.

Applied for Change of Status to H-4 (aproved) which is valid till June 13th 2014

H-4 extension application from June 14th 2014 is pending.

If a new employer wants to sponsor me now for H-1B, how will the process be from H1 to H4 to H1? I read in some forums that I have to go out of the country. Is that the case?