Has any foreign nationals residing in Japan been able to get married without at least showing their birth certificate at the city hall? How and where? It may
depend on home countries what documents are needed when a non-Japanese person gets married under the law of Japan;
experience of a foreign person of non-Australian nationality may not lead you (of Australian nationality) to a good solution.
Also, your situation and circumstances at present may differ from his/hers at that time.
So, I recommend that you would not rely on other persons' "solid examples" in the past but confirm what you should do now for this case.
You seem to have not yet got a clear explanation on this matter, neither from the Australian Embassy nor at a municipal office in Japan.
If you read Japanese, please check Questions 2 and 3 and the corresponding answers (, which are among Qs and As offered by Civil Affairs Bureau of the Ministry of Justice, Japan) on the webpage of this link.
http://www.moj.go.jp/MINJI/minji15.htmlRegarding this case of yours
: It sounds better for you of Australian nationality to prepare both your Certificates of No Impediment (abbreviated as "CNI") and your application form for it, plus translations into Japanese of these two documents each. (The translations may be made by yourself.)
: I suppose that your birth certificate is not required, because your date of birth and birthplace (= Hong Kong) are mentioned clearly by a consul in your CNI.
For a non-Japanese person to get married under the law of Japan, the following fact has to be confirmed
: the fact that the person meets legal conditions (such as age) for a marriage, i.e. he/she has legal capacity for a marriage, under his/her national law.
When the authority of the home country of a non-Japanese person does not issue a certificate of this fact, he/she seems to have to take his/her oath on this fact.
You take your oath on this fact by swearing in the application form for your CNI that you believe that you have no legal impediment in your marriage, i.e. you have legal capacity to get married.
The Australian Embassy seems to think that a CNI can work as a certificate of this fact under the law of Japan.
However, as you notice, in a CNI, a consul for Australia does not directly certify the applicant's legal capacity for a marriage; a consul declares, on the condition that the information which is indicated in the application form is true and accurate, that there is no reason for the applicant not to be able to get married.
So, you seem to have to prepare not only your CNI but also your application form for it.
You can find templates for translations into Japanese of these two documents on the website of the Australian Embassy.
http://japan.embassy.gov.au/tkyo/notarialjpnservices.html#T4