In the very beginning of telephony, there was no need to name or number the exchanges because there was no interconnection. You could only call people in your town, on your exchange, connected to the same phone company (yes, there used to be multiple non-interconnected competing telephone companies in some places. Philidelphia, for one, had two phone companies until the WWII era).
Before any automation, the call was established by you cranking your phone/flashing your hook, the operator answers, you tell her the number/person you want to speak to, they connect to the correct line (or trunk if the person being called was on a foreign exchange, where the foreign operator would answer, and the cycle would repeat until you were connected to the called line). The first thing to be automated were the inter-exchange connections, then local dialing, then finally DDD (Direct Distance Dialing) in the mid 60s IIRC. Prior to that, if you were on an automatic exchange but wanted to call long distance, you dialed a special code for the LD operator and told her who/where you wanted to call.
It is possible that at the very beginning, exchanges were only known by names, but those names are probably not the same names that were used as mnemonics, because they wouldn’t have translated to the ‘right’ numbers. For all intents and purposes, “modern” telephony has always had numbered exchanges, and the mnemonics were solely for the “ignorant” end-user to help them remember. Recall that in the old days, people weren’t commonly expected to remember long strings of numbers like we do today.
If you are interested, check out www.telecom-digest.org or privateline.com for lots of info about telephones and telephone history.