The actual answer to the question:
The first reference to the sword in the stone is to be found only in the prose redaction of Robert de Boron’s Merlin. Of the original poem only some five hundred lines survive. Considering that, and the way scribes could elaborate on their sources, we can not now be sure whether the sword in the stone featured in Robert’s own work or not. Whichever is the case, the work does predate the Vulgate Cycle and the other prose works important to this discussion.
(Toohey, Kathleen, King Arthur's Swords)
If anyone is interested, you can read the Prose Merlin online.
I have not found any historical reference to anyone pulling out a sword from a stone. I think this makes sense, because I imagine that it would be hard to put a sword there in the first place. Sarcasm aside, if you find a historical reference to someone pulling a sword our of something, feel free to let me know in the comments.
The following is in response to some of the things said in the original question.
I'm really sorry, but it is not a "theory" that the story of the sword in the stone originated from Arthurian legend. This is a fact.
The google document (why didn't you just link to the wikipedia page that the google document is copied from?) is a copy of the wikipedia page for the movie The Last Legion. This movie is "a 2007 Fantasy film" that combines Arthurian legend with roman history.
You say that
"Some say that it was based in Rome and Merlin first possessed the sword given and made for Caesar Augustus, who ruled in Rome in 27 BC until 14 AD. Passing down the sword to each generation eventually being thrown into a stone that only a true Caesar could pull out." That is only true in the movie The Last Legion, which, as stated previously, is a work of fantasy. This is not actual history.
The legend of the sword in the stone, minus the stuff about Caesar Augustus (which, as stated previously, is from the movie The Last Legion), is from Arthurian legend. T.H. White is the author of a children's book, which is also based on Arthurian legend.
The legend of the sword and the stone is a component of Arthurian legend. Arthurian legend is a collection of old stories about King Arthur. A common feature in many of those stories is the mini-story of the "Sword in the Stone", which features King Arthur pulling a sword out of a stone.