How did this split happen historically and halachically before Shulchan Aruch, and why is not like having two Torahs? Where is the source for the split?
Since there has been a Torah, there has been machlokes. Hashem, in His Infinite Wisdom set up a bais din to deal with this Devarim 17:8... See the ramban there. This is where all of Torah sheb'al pe is finally decided (Mishna sanhedrin ailu hen hanechnakim- I'll find the page later).
After the Galus of the Sanhedrin, there was more machlokes which was not finalized (for us) until Rebbi and then later the gemara was redacted. Of course the Yerushalmi had different opinions. So did Gaon vs Nasi, and so on. So communities just followed their local or long distance rav.
It's been a while since I did "lo sisgodedu", but from what I remember, it applies when there is only one bais din in town, if there are two, it isn't a problem. In the melting pot where many communities came over with their customs, this can be considered like multiple batei dinim. I'll try to source this later.
Davening a different nusach than your shul is a different issue of not changing the custom due to potential machlokes.
Theories abound on this particular split. The most popular theory is that the Ashkenazim originated in Eretz Yisrael and migrated to Italy and then up the banks of the Rhine River into Germany. The Sefardim originated in Bavel and migrated across North Africa and the Mediterranean Sea to Spain.
Much of the differences in halacha between early Ashkenazi and Sefardi authorities stem from the differences in their approaches to understanding the Talmud. There are those scholars who have suggested that some of their differences trace back to the differences in the approaches to explaining the Mishna between the Jerusalem and Babylonian Talmud. This would fit nicely with the theory as to the origins of the two communities.
What we often fail to recognize is that from time immemorial there was communication between these two communities. In some periods the communication was more frequent than others but each of these communities developed with some awareness of the other. I am not so sure that the stark differences we see in the written opinions of those times between Askenazi and Sefardi scholars necessarily reflect the reality on the ground of the Halachic practices of the average Jews of these two communities. Remember that they did not have the libraries we have and the empirical data of halachos and minhagim that we have today and many things that we do par for the course many of the scholars at the time of the Rishonim never heard of either because the customs had not been instituted yet or because of the lack of information.
It is not like having two Toras since these are the practices of two separate communities. The problem of Lo Sisgodidu, to which I presume you are referring is not a problem when it is in disparate communities. The idea of this prohibition is to not make separate groups in proximity of each other. The implications of how to deal with influxes of entire communities at once (such as Sefardic communities arriving in Germany in the late 15th century) or the ingathering of exiles in Eretz Yisrael and the disparate customs and practices has been dealt with by many great Halachic authorities throughout the centuries, from the last of the great Sefardic Poskim, such as Rabbeinu Shimon Ben Tzemach Duran (Rashbetz) of the 15th-16th centuries to current modern-day poskim such as Reb Moshe Feinstein, and Rav Shlomo Zalman Auerbach and LiHavdil bein Hayim LiHayim, Rav Ovadiah Yosef, Rav Y.S. Elyashiv, and others.
The essence of the question is although we recognize the need for homogeneity as expressed in the prohibition of lo sisgodidu, who has the authority to tell one community or the other to stop its practice and adopt that of the other? And if one may think (as some have) that we should create a blended community and take some from one and some from the other, who has the authority to decide for everyone on these matters? And what about the concept of minhag avoseinu biyadeinu, that one should uphold the customs of his ancestors?
A long time ago there was the concept of a community that had one way of doing things. If an outsider moved there he was required to take on the practices of his new community, whether more lenient or strict than those of his original hometown. Today, except for a few rare exceptions, such communities do not exist.