A good Q. and I remember answering it elsewhere, but others didn't like my answer so much.
We have a "loophole" in Halacha that's called Chazakah (a presumption) and it works in many many areas of expertise in cases we don't have witnesses or a trusted document. For example,
clothes or watches that you wear are presumably yours, if you work in a field for three consecutive years it's presumably yours, if you and your girlfriend come to a new community and cohabit with her you become presumably married, if a woman comes from far away and holds a child she continues to fosters for years he becomes presumably her son.
So if you're not a Jew, but come to a new community that can't check your background (very difficult nowadays) and keep the Torah and Mitzvos you become presumably a Jew by a Chazakah. Of course you'll be a sort of a "second-grade" Jew, a Jew without ancestry, but still a lawfull Jew.
It is very easy to visualize: think about driving by the countryside at late night and hitting a man. He's hurt and unconscious but nothing serious. He looks like a full-fledged Chassid - black coat, Shtreiml, white socks etc. When he awakens he remembers nothing and has no IDs. You post his picture on every social network but nobody recognizes him. He knows all the Halachos and keeps them piously. What would you do? Would you accept him into your community or suspect he's a masquerading gentile? Well, if he walks like a duck and quacks like a duck ...
The second part about G-ds acceptance, I think, is even easier, because it is commonly accepted that one who truly wants to be a Jew and keep the Torah already has a Jewish soul (why would he otherwise). So the conversion is always only a formal communal acceptance, just as a marriage.
THe sources for this statement are:
Rambam's ruling at the end of Melachim (): "משפחה אשר נטמעה נטמעה". Meaning that IF somehow a Mamzer was eventually accepted as a regular Jew, his descendant will always keep the status of regular Jews. So I learn Kal Vachomer, because a Mamzer is a strict prohibition.
Before Matan Torah there were no courts and everyone (incl our forefathers) just accepted Judaism on their own.
To your question - there's no other way to be accepted as a Jew if your gentile past is known to all.