DH and I started off as pen pals, in 1997-so all we had was pen and paper too! We still have each other's cards, letters, gifts from all of our years spent apart. We got into yahoo chat rooms when the internet became a big thing,but we'd still write pen and paper letters as well. It was momentous in our relationship when we could finally email each other! When we finally phoned each other, it was for 30 min for each person, to save on the phone bill. I used a phone card on my mobile and he had to pay the phone bill on the BT land line.
We didn't have Skype until my last year in the States, 2008. I'd wake up every Saturday morning at 6am, because that was....I forget what time it was in the UK, but, it was always better for me, because my roommate was gone, and I could have my time with DH. It was never easy, but, I knew it was never going to be. But, if you're both committed to it, it works out in the end.