'I was like,' stage 1
There are actually two distinct stages of development in the "I was like" locution. The earliest instances of the phrase in a Google Books search are from the late 1960s and early 1970s, and like serves essentially as a fill word or floor holder for the speaker. For example, from an article on Stan Getz in Down Beat magazine (1966):
"...Ralph later found out that the brakeman had gotten off the train to see why it had been stopped and had slipped on the ice and fallen under the wheels of a local train. He was decapitated, and he was, like, two weeks away from retirement. No job is that important where somebody's got to ... of course, it was an accident, and nobody can blame anybody for it, but I just got disgusted and quit."
And from an interview with an unidentified ex-soldier Roger Williams, The New Exiles: American War Resisters in Canada (1971):
I was like speeding, in the true sense of the word speeding, you know, a chemical reaction; I was so scared, I was really afraid of going to jail. ...
They didn't call me in after I refused to fight; I was, like, isolated.
This form of the usage goes so far back that it threatens to intersect with the even earlier beatnik use of like from the 1950s—"like, wow," for example.
'I was like,' stage 2
The second stage in "I was like" usage involves using "was like" as a replacement for a verb such as "said" or "responded" or "asked" or "thought." In Elephind newspaper database search results and Google Books search results, this usage emerges in the 1980s. One early example is from Christopher Nicholas, "Lesbian Life Normal for Students," in the [Washington, D.C.] American Eagle (January 22, 1982):
"When I finally came out to them my mom accepted it rather easily. I said, 'Mom, you always knew ! was different.' But she really didn't understand what I was talking about," Carol said. "She was like 'Wait a minute, wail a minute.' She didn't want this to exclude myself from doing anything with males."
From "Leimkuhler No 'Chicken'," the [University Park, Pennsylvania] Daily Collegian (March 15, 1982):
"When we played Cheyney," Leimkuhler said, "(Portland) [the Penn State coach] was walking around, 'Bawwwwwwk, bawk, bawk, bawk' like I was gonna be chicken and stuff again. And I was, like, 'Not this year.' And so I loved it. I faced her."
From "Best-Selling Soul Band?" in the Indianapolis [Indiana] Recorder (February 26, 1983):
When Charlie Wilson, the lead singer of the Gap Band, learned that his was the only soul band to go platinum last year, even he was surprised. "We checked. We thought maybe. Earth, Wind & Fire or Kool & the Gang would have been there, too," said Wilson. "I was, like, wow! all those people walked past all those other albums on the rack to buy the Gap Band record."
From John Shanley, Danny and the Deep Blue Sea: An Apache Dance (1984):
ROBERTA. I wish my father would die. He was the one who made me get married. This guy I know got me pregnant. I was like eighteen. And my father made me get married to him. He wasn't a bad guy. We moved into this apartment. ... And then my parents started comin over all the time. ... And this guy, my husband, he was like, What the fuck is goin on? His parents were cool. Just like called once in a while on the phone. I felt so bad. Sick in the morning. Mother knockin on the door by twelve o'clock. My father comin in after work. And the guy, my husband, when he got there. It was like, Who the fuck are you?
From Peter Blautner, "Hard-Core Kids," in New York Magazine (May 26, 1986):
"I was like, 'Whoa,' when I got that," Frank says. I sat down and wrote back to her, explaining all the options of what she could do as fully and clearly as I could, and tried to leave the decision to her."
She was drunk, and she approached Jimmy boldly. He suggested they go out to a van on the street, but then realized he was drunk himself. "I was like, 'I'm gonna rock your world, and you can't remember what your van looks like?'" Natalie says.
From Marie Ferrey, "Pat Mead: A Voice from the Pipeline," in U.S. Black Engineer (Fall 1990):
It was something if you were on the subway [in Manhattan near Polytechnic University] and a brother said something and he was American. You just expected people to have an accent. I remember one day I was on the subway, and this guy said something to me. He was American, you know, and he sounded like he was from Alabama....I was like....Praise the Lord!
And from an interview with J Mascis in Spin magazine (February 1993):
SPIN: I heard you did the soundtrack for and had a part in the film Gas Food Lodging. How was that?
Mascis It was cool. The director, we talked for a couple years. She came to one of our shows once and I kept in touch with her. She was all, "You should be the band" and "You're so great," and I was like, "That sounds lame—why don't you just put me in the movie?"
A crossover form appears in what appears to be an interview with Horace Silver, in Jazz Times, volume 24 (1994) [combined snippets, quotation not shown in viewing window]:
It was like a great little game, because that's all I had to do was ask him to play the bridge, and he was like saying, well that's all you have to do is ask me, and I'll play it. We were just hangin', one of those hangs that goes until sun up.
In this instance like may be serving as fill word, or it may be on the verge of rendering the following word (saying) unnecessary in the new speech pattern.
The first stage of "I was, like," usage seems to have arisen in the late 1960s and early 1970s, and consisted of using like as a placeholder or space filler in much the same way that y'know often is. The second stage of "I was like," where "was like" replaces an indeterminate simple past-tense verb (such as said or thought) appears in Elephind and Google Books search results as early as January 1982, but became truly widespread only in the early 1990s.
I didn't search for instances of "I was all"—although one popped up in the 1993 J Macis Spin interview, anyway—but in my memory, at least, it arose fairly close on the heels of the second stage of "I was like" usage. Where that usage first arose is unclear; still, I find it interesting that two of the earliest instances reported in Google Books search results (and cited above)—the ones from from 1986 and 1990—are from New York City. And the earliest match of all—from 1984—occurs in a play set in the Bronx (a borough of New York City). It is at least possible, then, that the stage 2 "I was all" usage arose in New York City, rather than in, say, Southern California—despite the fact that many people associate the speech pattern with Valley Girl talk or related SoCal syntax.