How far back did unmarried people live together without fear of local authorities or religious types?
As an occasional thing? Probably forever. There have always been people who were too rich and powerful for the authorities to trouble them or too poor for the authorities to bother themselves, over.
As a recognized social phenomenom in Europe and North America, it began slowly in the late 1960s and has gained ground every year since.
Pesonally, in the mid 90s, I was surprissed to learn that it had become socially permissable for senior citizens such as my grandfather to “live in sin” Not that I had a problem with it, I was just surprissed to learn many didn’t.
Historically, it appears that it was more common than you might think.
Sexual Revolution in Early America by Richard Godbeer is on point:
I am guessing also that in sparsely populated regions, such as the American frontier in the 1800s, it was probably somewhat frequent. Preachers and churches were somewhat scarce at times, and records are patchy at best. (Sometimes a family Bible is the only record of a marriage.) I’d say it happened now and then that people just assumed a couple were married when they had never actually stood in front of a preacher or judge.
Slaves in the South before the Civil War often weren’t allowed to marry. Either they preformed their own ceremonies (such as the fabled jumping-over-a-broomstick) or just lived together as man and wife without benefit of ceremony. Considering a couple might be seperated at any time, a til-death-do-you-part marriage wouldn’t be practical.
We don’t know all that much about the poor in urban areas during the Victorian Era in some cases-- their lives went mostly unrecorded. There is this article, (which, of course, take with a grain of salt.)
This site (an excellent resource for Victorian letters, articles and books, even if some of them were exaggerated at the time for shock value) is The Morning Chronicle : Labour and the Poor, 1849-50; Henry Mayhew - Letter XII
It seems to have been common for poor people to live together without marriage for pretty much always. I have a book that documents quite a bit of it in Victorian times, and it was only more commonplace before that. And of course there have always been mistresses established in homes of their own and whatnot.
For middle-class types that were supposed to be respectable and religious and whatnot, it was a very scandalous thing to do in the late 1800s. Some people did it, though; a few well-known writers among them. And remember that the ‘free love’ movement started in the 1800s, too, among outspoken but middle-class people!
It was still scandalous in the 1920s, and sometimes done as a philosophical, conscious society-flouting sort of thing. That continued for a while, and it wasn’t until the 1960s that it became at all common.
It was more acceptable in some places than others. My grandparents have been “living in sin” in a small surburban town in central France since the late 1940’s or so (my “real” grandfather died in WWII, and the “new” gradfather raised my dad). During this whole time, my grandmother kept her job as a local schoolteacher, so it doesn’t seem to have created any scandal of note.
An interesting question…but as I think some of the respondents have alluded to, you might also ask “when did people have to be married to live together?” That and the other question “who is actually married?” In many times, in many parts of society, living together was pretty much the same as being married. (The shame…for the woman of course, was in having sex with a man who would not openly aknowledge her.)
/hijack
Richard Godbeer?
That guy has got the coolest name ever. Dick Godbeer. That’s just effing awesome. (I think I saw him before on the History Channel).
/end hijack
The Catholic Church did not ask for marriages to be performed in a church and with a priest as one of the witnesses until the Council of Trent (XVI Century). This was because, by having a person who could write take down an actual record, it was a lot easier to prove whether you were married or not. In spite of what most people think, the marriage IS NOT performed by the priest (I repeat, he is merely a witness) but by the couple. By Catholic Church law, a man and a woman living together are married if they consider themselves to be so and/or it’s public knowledge that they live together. Any baby she gives birth to is considered his and legitimate, etc.
I have in front of me an old article about the thesis an LD student wrote for his degree: it was a study on all the cases that went before Church Judges pre-Trent, from the Kingdom of Navarra. It was less than 20 cases, and in each and every instance it was a case of the wife suing the husband for abandonment - he was either trying to become a monk or to marry a younger model. In one instance, the woman claimed that even though they hadn’t actually shared a house, her 3 kids were his. The judge took one look at the kids’ faces, verified that the defendant was, indeed, a single child and ad no known male cousins and failed for the woman 
In another case, over 50 people were called as witnesses - there were more witnesses saying that those two were husband and wife than saying they weren’t so again the judge failed for the wife. In any of these cases, being able to show a piece of paper would have saved a lot of headache.
Of course, when you didn’t have a piece of paper it was also a lot easier to get a mutual-agreement divorce 
Welcome! 
Your post is noted, & appreciated!
You may have a future here, kiddo.
My parents have been living in sin on and off since 1973.