Вероятнее всего, союзы, как и предлоги, произошли из значимых слов.
Например: я буду около (= рядом - наречие) -> около дома (предлог);
где у него перед (=передний край - существительное) -> перед домом (предлог);
местоимение "что" -> союз "что".
Однако есть предположения, что слова, ставшие теперь сюзами, когда-то были чем-то вроде знаков препинания, показывающих, что предложение началось или закончилось (и тут можно вспомнить школьную классификацию союзов и предлогов на производные и непроизводные. Если выше речь шла о первой группе, то теперь - о второй). Когда два предложения соединялись в одно сложное, эти слова оказывались на их стыке, соединяя их. Потом эта функция стала основной.
Подробнее об этом и о периодике переходов слов в союзы в славянских языках можно почитать в этой замечательной статье, но однозначно ответить на этот вопрос сложно, так как в любом случае этот процесс происходил так давно, что у нас нет никаких письменных или иных свидетельств этих изменений.
Что касается языков без союзов, то их практически нет в так называемых инкорпорирующих языках, то есть тех, где одно слово путем сложения корней имеет значение целого предложения. Например, в папуасском языке йимас (Папуа — Новая Гвинея) есть слово
paŋkrakaykaykaykwalcampikulanaŋtalkiantuŋkt — примерно «мы, несколько человек, встали и быстренько пошли». В таких языках просто не нужно так часто выражать отношения между частями предложения или словами, как это нужно в наших языках.