No crime and marriage certificates should be done in Shanghai. Ask Notary Public (gong1 zheng4 chu4) for details.
For birth certificate, you may also ask them for suggestion. Usually, birth certificate is only issued by the hospital where you were born. But in China, nothing is impossible, you know.:-)