Applied TPS on late august, and I applied AP on late December because my parents are not doing well. When applying for AP, I included the Doctors note and a letter and mentioned EXPEDITE. But looks like my expedite request was not accepted.
But I guess I need to go back very soon. So, can I travel when both TPS & AP is pending. My h4 visa is still valid till 2017.
Any suggestions?

if h4 is valid you can travel, but your application for AP and TPS might be considered withdrawn, why dont you take infopass, show same documents and they will grant you infopas on the spot if yoiu have all supporting documents...

Go to your nearest field office. They will print your AP on the spot. If walk-in go early. Its best to make an appointment.

@Saiko
You need to carry the following documents to your nearest field office for Emergency AP Request.

1. Emergency Advance Parole Request Letter- Write the formal letter maintaining your current status (TPS Pending) with the date you have filed the application and the emergency reason for your visit with your signature and date at the bottom.

2. Original Passport, Driving License/ State ID, SSN (If applicable)

3. Employment Authorization Document (If you have already received from USCIS)

4. Copy of Bio metrics Appointment Letter (If you do not have the Bio metrics letter, you might have to take bio metrics again.)

5. I-765- Application of Employment Authorization Receipt

6. I-821- Application of Temporary Protected Status Receipt

7. Recent I-94 and Travel History ( Print it from https://i94.cbp.dhs.gov/I94/consent.html)

8. Travel Itineary (Ticket Reservation Copy)

9. Medical Letter from Doctor in the Hospital Letter Head

10. 2-Passport size photos (Take it from Costco/ CVS/Walgreen)

Carry all these documents and explain your situation calmly to the immigration officer, you should be fine. Technically, you can travel now too because your H4 visa status is still valid.
It is not true that every TPS holder requires AP to travel.
For example- A person in H1 with TPS can travel on his/her valid H1B visa and does not necessarily require AP. TPS and H1/F1 are completely two different universe. One will enter into the grey area once the TPS EAD is being used. Until TPS EAD is used, both the status remain active.

Below is the extract I copied from- http://www.immihelp.com/greencard/adjustmentofstatus/eadap-hl.html

"Just receiving an EAD/AP does not change the non-immigrant status in any way, and he/she is still on H or L status; thus, the person is either in EAD/AP status or in H/L status. As long as a person maintains an H/L status (H/L status not expired, H1/L1 holders working only for their sponsoring employer, and H4/L2 holders not working at all), he/she can travel outside the U.S. and come back without the need for advanced parole even after applying for an adjustment of status."

@ohio Thanks for the information.
I have an infopass appointment scheduled next week. I did not know that they can print AP on the spot like @furke mentioned. Hopefully they do that.
I will update what happened after the infopass.

Oh, I forgot to mention the below things.

They will give you one time entry only for emergency purpose. They will ask you for the duration of AP. Be prepared for that, give them the genuine time frame. Ideally 2 months should be fine.

They will give you two papers- one you need to submit to the transport line and the other is AP that you need to present during your arrival at port of entry which has your photo attached.

@ohio What do you mean "the transport line"?

Transport Line Paper indicates that you need to give that paper to the airline officer while you check your baggage. But if your passport is valid they won't even take it, I believe it is for those people who passport is expired but has an AP to make a travel.

Thanks for the explanation. Got it.

Update: No-Luck on getting the emergency advanced parole from the USCIS field office. They only provide AP for life/death situation, not even for serious illness.

Finally got my AP (took 66 days for it to arrive).
Now my question is:
- While returning to US do I have to use my H4 visa or AP at port of entry?
- Or should I show both to the immigration officer there?
Any information...!

As per my understanding, If you use AP during your return, your status will be parolee status. But if H4 visa is shown at the port of entry, your status will be in H4.-(Assuming that you have not used your TPS EAD.)

If you need to travel frequency, H4 will be the better option, if you don't plan to travel that often then AP can be used as an alternative option.

TPS EAD has not been used yet.
I applied for AP just to not-abandon my pending TPS application. Will be traveling to Nepal once a year.

So after the TPS is approved and I start to work after returning from Nepal, my H4 will be void, and for traveling I will need to apply for AP again? Is that how it works?

Since you have a valid H4 visa, I think you can choose between H4 and AP, which one to use. AP is for those who does not have other option to re-enter united states such as expired visa.

But the debate is what will happen later at the renew time? During the initial application, the requirement was that you must be Nepalese Citizen and  must be in united states on or before June 24. So, during the renewal, you just have to give them the same set of documents.

Once you are into parolee status, one has to go back to home country to do the adjustment of status to revert it back into H4. The question is how difficult will it be for the change of status. If your primary applicant, H1 is in the Green Card Process, it would be wise to maintain H4 visa.

I am more concerned about the change of status if the renewal doesn't happen.
Are you sure that one has to go back to home country for the adjustment if the renewal doesn't happen. Primary applicant GC process has not started yet, might take a couple of years. That is why I was thinking of working on TPS EAD.

I am almost certain that adjustment of status should be done in the home country, the bottom line is if your TPS is still pending (EAD not being used) then technically you are still on valid H4 Status and you should be able to use H4 for your entry.