What is the process for a person who has left Judaism and converted to a different religion, who now wishes to return to Judaism? I have heard (based on an Avos D'Rav Nosson) that he would need a second circumcision and Mikva. Is this true?
I am unfamiliar with the Avos d'Rabi Natan that you seem to be referencing. However, the Rema says in Yoreh Deah 268:12 that an mummar (Apostate Jew) who does teshuvah need not immerse.
A second circumcision-like procedure is definitely not required! It's better for the person to dunk in the mikva again as part of re-emergence into mainstream Judaism.
This is quoted in Rabbi Aryeh Kaplan's The Real Messiah in regards to a born Jew who gets into Christianity and then (spiritually) comes back home.
In discussing the emigration of Ethiopian Jews to Israel several decades ago, Rabbi Benzion Uziel (the then Sephardic Chief Rabbi) advised they all immerse in a mikvah, if nothing else "as part of acceptance into the mainstream" (I think his language is something like kabbalat divrei chaverut or the like), as their practices of Judaism had become somewhat warped over time. Rabbi Uziel mentions a record of a large group of former Karaites reconnecting to Judaism some 800 years ago, with a mass mikva-immersion event supervised by Rabbi "Avraham HaNagid" (the Prince); believed to be Rambam's son Avraham.