How was time each customer spent on the phone calculated/recorded in the time before there were computers to handle calls (and therefore, I assume, billing)? I assume that the actual bills were sent through the mail.
Initially it was all done with billing cards that were hand written by the switchboard operators. This quickly became unwieldy and Calculagraphs were used. Wikipedia has a general description of them. Basically a calibrated timestamp mechanism. This is a Bell System Practice from 1926 that describes the mechanics of one of these devices. This goes into more detail than you could possibly want.
Automatic switching systems by design necessitated a different kind of billing for message telephone service where you were billed per call placed. There were registers associated with each line appearance that indicated the number of calls placed.
With the advent of Direct Distance Dialing (DDD), basically the method for automatically dialing long distance numbers as opposed to operator assistance, an automatic system was required. This is what's called AMA or Automatic Message Accounting. It's either a local or centralized service that used punch cards or punched tape to account for every call placed. Calls were tallied by a computer system and then bills were sent out. It's an extremely complicated system. The patent for the initial system, filed in 1955 and granted in 1960, is one of the longest ever issued at 620 pages. The Wikipedia page gives a bit more detail about the system.
As far as how people received their bills, I have to assume they were sent through the mail but I don't know this for a fact. I can't think of any other way for it to work.
Other than what I linked there's two references that can give copious amounts of information on the topic, much more than I can get into here. The first is Fundamentals of Telephone Communication Systems published in 1969. You'll be hard pressed to find a copy of it but it has been digitized. You can find it here: http://etler.com/docs/WECo/Fundamentals/
The other which you can find in most big libraries is called A History of Engineering and Science in the Bell System. It's a seven volume series published by AT&T and Bell Labs in the early 1980s that covers pretty much the entire AT&T and Bell Labs history of research and development from 1875 to the time of publication. I don't have them in front of me right now but the volume on the Early Years would give you information about billing back then. The volume on Switching would likely have information about AMA.
/u/bg-j38 presented the North American side if the matter, so let me present the continental European solution: impulses and counters.
The numbering was divided between local and long-distance, sometimes near-long-distance up to 100km as a discount zone. The difference between them was simple: if long distance prefix was dialed (16 in France, 0 in Germany and Eastern Europe, 8 in Soviet Union), then it was long distance.
Now each telephone line had an impulse counter. A simple mechanical device that increased its value by 1 upon receiving a "tick". Local calls were charged one impulse per call (from mid-1970's one impulse every 3 minutes), and long distance were charged different frequency of impulses, later (from mid 1970's) depending on the time of the day and the destination. Example, Poland, 1983: peak time long distance cost an impulse every 5 seconds, off-peak every 10 seconds. So long distance was 36 times more expensive than local. Germany and France weren't as drastic, but the billing system was 100% the same.
The price of the impulse, or "unit", was fixed. Only operator-assisted services could charge arbitrary amounts , but on the other hand operators went out of use in Europe much earlier than in North America.
This system lasted well into late 1990's.
Sources: French, German, Canadian and Polish phone books from 1977 to 1998.