It's been present since the beginning. To see that, get the source from alt.sources, specifically the message titled "Python 0.9.1 part 17/21". The date is Feb 21, 1991. This post included the grammar definition, which states:
for_stmt: 'for' exprlist 'in' exprlist ':' suite ['else' ':' suite]
You might be able to find the 0.9.0 sources if you try harder than I did, but as the first public release was 0.9.0 on 20 Feb, that would get you back one day. The 0.9.1 release was a minor patch that did not affect this part of the grammar.
(Is that a UTSL reference or what? When was the last time you looked at a shar file? ;)
BTW, I reconstructed the original source and tweaked it a bit to compile under gcc-4.0 on my OS X 10.4 box. Details for those interested few, including python-0.9.1.tar.gz.