Pre-iPhone phones, for example Nokia phones with Symbian on it, did allow you to install applications. I remember when I was in middle school with a Nokia N70 exchanging games with Bluetooth with my friends. Who had internet at home (that was only a bunch of people) did download games from forums and then send to everyone else, as well as music and videos. Same for other models of cellphones, they all had some sort of application format.
Then the first Android devices arrived, with the Android Market (long before Google Play) that did allow you to download apps. But most people again maybe they didn't have internet, or more simply wanted pay apps but didn't want to pay for them, just exchanged .apk like it was the norm. (Pirating by the way was much more present than these days, for example I don't recall a single person having a PlayStation without the modchip, and burned PS1/PS2 games where the norm).
It's only with the arrival of the iPhone that this was no longer possible. In fact I recall that the criticism of the first iPhones, till the iPhone 4, was that it was an overpriced device and that it did lack of the possibility to install applications and exchange files with bluetooth, like everyone was used to do. The iPhone was a niche product that was not diffused (when I was at high school I recall maybe 1/2 people having iPhones, all other one Android devices).
The thing on cellphone operators is maybe an US specific thing, I don't recall having anything like that in Europe, more specifically in Italy. Quite frankly till 10 years ago using the cellphone network for internet was unthinkable, because the prices where so high. Then arrived the contract that give you 100Gb of data a month for 10 euros, but back in the day internet was expensive, to the fact that just by pressing the internet button on a phone it did consume all your credit. This is probably also the reason why WhatsApp become so popular (you could chat with your home internet connection that now everyone had without consuming expensive SMS)