[Morromist]

Ok, I'm pretty sure

3D Monster Maze (1981)

used an autotile system -albiet a very very different sort, that made 3d-looking tiles appear in the correct place. Is that a proper autotiler? I don't know, but the principle is pretty much the same.

Anyway I'll bet there are old games still that are out there with auto-tiles.