Well, the only thing that the stamp did was allow for mail prepaid by the sender. Certainly turned out to be significant (it created the ability for there to be junk mail, for one), but people certainly sent letters before there were stamps. Think of the mass of epistolary novels that were written in the 18th and early 19th centuries.