For you ALL
You have lot of choices
1) You can go back home and apply for H1 VISA at the back home US consulate. Most likely H1 visa does not get denied if you have all the papers and you never been out of status. However, if you are the nationals of certain countries especially any muslim country (not only those 26 countries), you wil have to have Security background checking before they issue your visa. It is taking more than 2 months now a days. I know people in my country (Bangladesh) waiting for more than 70 days for VISA. They are approved, yet they are waiting for the stamp. This is frustrating as they no H1B worker has that much vacation. It may drives those people loose the job. However, if you are from INDIA you should not be worried, your visa stamp will be given on the same day. You can also take the visa from Canada or Mexico. Indian nationals are still taking VISA from third countries. If you are national of any Muslim country, please think twice and plan to wait for a long to get VISA from back home. You can also revalidate your visa from US, but it takes lot of times what you gusy dont have.
Please keep in mind, even though you already used EAD or AP, you can again apply for H1B visa at consulate if you are still working for H1B provider company. This is little foggy area. So make sure with your lawer.
2) You can travel on AP. Assuming you have applied for AP, but you are not sure when it will come. Take the I-485 and AP receipt notice and walk in local INS, explain your situation, you will be given AP within a week or so for sure. If you have not applied for AP, but applied for I-485, and does not have visa stamp, take the I-485 receipt notice and fill up the form of AP, and walk in local INS. Explain your situation, you will be given AP within a week. If you take AP, please take EAD just to be on the safe side. You might need that after you use AP.
If you stay in the same company, you do not need EAD aftre using AP. Yet, this is foggy area too. So take EAD when you take AP.
Let us know, should you guys have any more questions.
I am not a lawer.