That's a bit misleading— paper has been invented for centuries, if not malenia, but it's paper made from wood that's recent.
Stone, papyrus (woven in several layers; Egypt only, I believe) and cotton rags are what come to mind. Cotton rags turned into pulp and dried were used in paper making in the States during the Revolutionary War. There's also animal skins, which is what Wiki says parchment was made of.
Basically, anything that could be written on (ink optional; some messages could be carved) could be considered "paper".
A writer is a world trapped in a person— Victor Hugo
Ink is blood. Paper is bandages. The wounded press books to their heart to know they're not alone.
