What if I fail to receive FAA Medical Certificate via mail? My AME just called to let me know that my FAA Class 3 medical certificate had been issued and was sent to me via airmail from United States to China. Since April 7th, 2014 when it was dispatched, it has been over 2 months now and I still don't receive the certificate.

I called local postal office and was told I needed to find a 13-digits tracking number (e.g. AB123456789CD, 13 digits, with 2 alphabetic letters at the beginning and end of the string and 9 digits in between) of the mail so they could check for me. The problem is I don't have it and I have no idea where to find it on the https://medxpress.faa.gov website.

Can anyone help me on how I can get this number? What are my options should I fail to get ahold of the certificate?
You're really asking a postal service question (and from my experience with the postal service you're probably out of luck, even if you had the tracking number: Unfortunately when the USPS hands packages off to other nations' postal services that's often the last tracking update - either the item gets to its recipient or not, but it's gone into a black hole).

In any case the answer to the aviation/FAA half of the question ("I haven't gotten my new medical certificate yet - what do I do now?") is much simpler, and involves more helpful people than international mail: "Contact the Medical Certification branch" (see here).

In this particular case you want to actually call them on the phone and speak to a human being to determine (a) if they have a tracking number, and (b) how to proceed to ensure that you have a valid medical certificate in your possession.
I know in cases like this the Medical Certification branch can also fax you a copy of the certificate (I believe these are valid for 60 days) while you try to get things straightened out and get the actual paper certificate in your hands.