Clementine

Clementine, along with several other new tunes, debuted on the Dead's Northwest tour of early '68, which they were recording for the Anthem album.....however, it never appeared on that album, nor on Aoxomoxoa, though it would have fit in well on either record. The Dead apparently weren't too happy with it and seem not to have played it very often.
Clementine was a rare Lesh/Hunter tune, so I'm not sure how much Garcia was involved in the composition. There's quite a difference between the way they played it in early '68 and how it sounded by early '69. It's strange that the song was left unfinished (if it was) since Lesh was a stern taskmaster on his later tunes!
In its shuffling jazzy two-chord rhythm, it's very similar to the Quicksilver Messenger Service instrumental Gold & Silver, which QMS had been playing through '67, so they may have influenced the Dead in this tune. (Which may be one reason the Dead never released it.)
https://www.youtube.com/watch?v=aPzTBtF0vY8 
Another likely influence is John Coltrane's treatment of My Favorite Things, which Lesh admired:
https://www.youtube.com/watch?v=qWG2dsXV5HI
The jazz feel is prominent in the Anthem '68 tour, between this song and the Spanish Jam and the whole jammed-out treatment of the new songs; but a jazzy style didn't really resurface in a Dead song until Eyes of the World a few years later.

The first recording on 1/20/68 fades in (probably out of a missing Cryptical), and it's given the full '68 treatment, especially with washes of organ from Pigpen. Along with other recent tunes like the Other One suite and New Potato, they get the verses over with quickly and then spend a few minutes wandering in a jam before dissolving into the next song. I'm sure audiences at this tour couldn't tell where one song ended and another began, since nothing would be familiar to them!
http://www.archive.org/details/gd68-01-20.sbd.jools.19470.sbe-fixed.shnf

We have a couple more performances from this tour, on 1/23 and 2/2, which are similar but longer, with quieter Pigpen. In each case Clementine comes out of Cryptical, a smooth transition in which it starts quietly; and on 1/20 and 1/23 it shifts into New Potato Caboose, which also works well. (On 2/2 they abruptly switch to Schoolgirl instead.) In the Cryptical>Clementine>Caboose medley, the style of jamming is very similar in each song, so it's almost like one long extended composition. (In contrast, the Dark Star>China Cat>Eleven medley sounds more like what it is, three tunes jammed together.) After they dropped Clementine, they kept the Cryptical>Caboose segue which flowed very nicely.
Some people prefer the 1/20 Clementine, but it seems like a tryout to me - I think 1/23 has the best version of this tour. It has a long intro, and it seems more developed, especially Garcia's playing. There's a very nice solo, and he returns to the verse at the end. On 2/2 they follow the same pattern - this version is the most focused, and just glides by with a hypnotic Lesh riff.
http://www.archive.org/details/gd68-01-23.sbd.jools.20347.sbeok.shnf
http://www.archive.org/details/gd68-02-02.sbd.jools.15801.sbeok.shnf (The 2/2 version was included on the So Many Roads box.)
(Note that new Miller transfers of this tour are now available, so "check for other copies" of these shows on the Archive.)

They may have played it on other shows of this tour, but too many tapes are missing to say for sure. It is perhaps the least-played song of the tour though, which shows that they may already have been unsure of it and perhaps decided it wasn't good for the record. I think they kept playing it throughout '68; but since so few shows were recorded, we only have a few brief snapshots from that year.

Clementine did resurface a few times, though....in a studio jam from 8/13/68 which was a bonus on the Aoxomoxoa CD reissue, they play Clementine for a while. They were starting to record the Aoxomoxoa album and were perhaps trying out ideas. This is perhaps the best early studio session we have; in most of our studio outtakes, the Dead are too focused on rehearsing to explore the jams. This Clementine is an especially nice recording, taken much slower than it was in January, but without new sections yet - with Garcia "singing" the melody lines on his guitar, it resembles Santana's style!

Clementine pops up again in a Hartbeats studio session on 9/21/68, when Garcia & Lesh jam on it briefly with another guitarist who solos over the chords. (Just the basic riff, not the full song.) It's odd to hear Garcia dueting the lines with someone besides Weir; it makes it sound like one of the club-blues jams that were very common in '68.
http://www.dead.net/features/tapers-section/september-17-september-23-2007-0

Which brings us to one of those clubs, the Matrix, and the Hartbeats' appearance there on 10/8/68, minus Weir and Pigpen. They start the show with Clementine (after Garcia sorts out some amp trouble), and it's basically a loose duet between Garcia and Lesh....kind of interesting, but with Weir gone, there's a huge hole in the sound. It takes them a while to get going - this Clementine is rather sloppy and unfocused - and things get more interesting after they turn into the Eleven. (Also in my opinion, this is the least interesting Hartbeats show, with Clementine pretty much just a warmup.) But here we start to hear hints of how it would sound in '69, with Lesh introducing new riffs into the tune and Garcia exploring different playing styles.
http://www.archive.org/details/gd68-10-08.sbd.belaff.17691.sbeok.shnf

The main bridge riff Lesh added was apparently taken from the bassline of Coltane's take on Greensleeves, from the Africa/Brass album: 
https://www.youtube.com/watch?v=nK265pszTvA 
This also suggests that Lesh had Coltrane in mind when he was composing Clementine. This riff sometimes recurs in Lesh's playing in later years - for instance, a bit in the 4/26/72 Other One (on Hundred Year Hall), or the 11/19/72 Dark Star. (I've also put together another post with more thoughts on this.)

The bridge riff also pops up in the next Hartbeats show on 10/10 - the second big jam, track 6, mixes this with some themes from New Potato.
http://www.archive.org/details/gd68-10-10.sbd.miller-ladner.4513.sbeok.shnf

The 10/30/68 Matrix show has a much more solid version of Clementine - in fact, you could use the start of this as a 'karaoke' version, since they're playing the basic backing just as if Garcia was singing. Here you can tell they're playing it in the new format, with the extra chords in the verse, a new bridge, and Lesh's distinctive riff afterwards. So it's frustrating not to hear how it sounded at Dead shows in late '68.... Once again, they head into the Eleven.
http://www.archive.org/details/gd68-10-30.sbd.sacks.1205.sbeok.shnf (track 11)
Also, in the post-Elvin Bishop jam (track 17), Lesh & Garcia go off on another Clementine jam, this time entirely based on the new bridge riff.

According to setlists.net studio dates, the Dead worked on Clementine several times in the Aoxomoxoa sessions in fall '68. Sadly, none of these outtakes have surfaced, but the Matrix shows make clear that they must have been working on the song around that time, and it appears in the two earlier studio rehearsals we have. Unfortunately, there are no Clementines in the Dead shows that survive from late '68, and they decided not to put it on Aoxomoxoa. Perhaps they felt it was too derivative a song, or Garcia wasn't comfortable with the lyrics, or the arrangement never satisfied them? It seems the song was left unfinished, never finalized...

But Clementine makes a final, unexpected 1969 appearance (kind of like Rosemary's sole surprise showing on 12/7/68)....again being recorded for a possible live album, on 1/26/69 they start with the Cryptical suite, which in the other shows of this tour could segue into any other tune, but suddenly they have a '68 flashback and go into a slower-paced Clementine. It's quite different from the early '68 versions, they've worked on it some more with Tom Constanten: his playing is very different from Pigpen's and he gives it that baroque-'69 flavor. Garcia matches his playing to Constanten's, and the intro and verse are very dramatic. They've also added some chords and new sections (as we heard on 10/30/68), and heightened the dynamics of the song; there's one wonderful solo section after the first verse where Garcia swells up one note at a time. Although he's a little uncertain about the verses (adding an extra solo when he forgets the second verse), the song abruptly transforms into a marvelous jam. At first it's built around the new riff that Lesh introduced at the Matrix shows; then they return to the two-chord waltz and Garcia starts a new jam theme - and the song ends dramatically with Weir, Garcia and Constanten all playing arpeggios around the chords. For a few minutes it's like being in the middle of a '69 Dark Star; but it fades and Garcia starts Death Don't Have No Mercy, abandoning cold Clementine for the blues.
http://www.archive.org/details/gd69-01-26.sbd.kaplan.2246.sbeok.shnf

After such a wonderful performance, it's a shame we don't have any more Clementines. It seems like if they'd kept playing Clementine, it could have become one of the highlights of 1969 shows; but just as with New Potato Caboose, they felt done with it, and it was never heard again.