I am not an wefugees expert but I will try to give an advice through my little experience in Germany.
1. Country of origin( Jamaica,Angola,Bangladesh,North Korea etc.) In each country there is Register office or department where you have to register your marriage. Certificate and letters from Register office are one of a concrete proof that Authorities in Germany accept.
2. GERMANY EMBASSIES. People can make appointment and take certificate and any letters from Register office to the Embassy. Then the Embassy will write an extra letter to back up your documents and stamp on it. You will have to pay some fees for that service. With this service you don't have to be there yourself because your aloud to use representatives like sister,brother,guardian, lawyer etc.
3. ASYLUM APPLICATION.
Regarding asylum application I don't . See a lawyer or pro asyl organisations for more advice on this Asyl matter. You wife can do it as well from Germany.
4. FAMILY REUNIFICATION
This is another option for you because your already in Germany. But you will need to have a strong evidence to convince Authorities. Examples the check my 1 and 2 opinions. Many foreigners in Germany lose their rights because of a very simple issues. We are here in Wefugees site to help one another.
Try to check Germany laws regarding work permit. People apply fo Asyl have different law from others groups like visitors,students and other people from EU members states.
I hope this will help in your situation.
I wish you all the best