Designing a novel way of walking for extraterrestrial animals is complicated. I tried my hand at designing gaits for large hexapodal creatures (see the main Furaha site), radial walking patterns and also explored walking with an odd number of limbs. In all such efforts the trick is to achieve something that looks interesting as well as believable. In the context of speculative biology 'believable' is balanced somewhere between 'Earth normal' and weirdness. One thing is clear though: you cannot get a believable result by assembling an animal of leftover bits and pieces, such as just sticking an extra leg on the end of a long tail.
Or can you? As usual, evolution on Earth manages to come up with designs that, if invented by a mere human, would fall in the category of unacceptable weirdness. The following video shows an insect that looks odd, but oddness by itself is fairly normal for insects. Look how it moves: most of the time insects walk with a double tripod gait: the front and hind legs on one side move in unison with the middle leg on the other side. When these three legs touch the ground they form a stable tripod. The other three legs meanwhile are lifted and swung forwards, and when they touch the ground, they will form a tripod as well. The two tripods are exactly out of phase, so when one hind leg is on the ground the other should be in the air. Now have a look at the hind legs of this interesting beastie, a trilobite beetle from Borneo. The original is here.
Its pairs of legs are in phase, a bit unexpected, but slow-moving insects can do that. But that is not all: it uses the tip of its abdomen as an additional unpaired leg. It curves its abdomen forwards, plants its 'leg' on the ground, and pushes backwards with it. Anatomically this may not be a proper leg, but functionally this animal certainly uses seven legs: it's a heptapod!
Here's another video. The beginning shows that this species can also walk with the front legs out of phase, but you do not get to see all legs that well. It is clear though that it uses the end of its abdomen as a seventh functional leg.
Why do these animals walk in this weird fashion? The gait does not look quick or agile. In fact, the animals appear to be rather slow and clumsy. A bit of research points to an answer. These 'trilobite beetles' are said to belong to the genus Duliticola, and using Google with that name results in a paper starting with the brilliantly surrealistic sentence 'There are two trilobite larva species in Singapore.' Apparently, the male and female of these species differ greatly in shape: the males look like typical beetles while the females are neotenous. Now neoteny is a condition in which sexual maturity occurs while the body is still in a larval stage. The axolotl is a famous example, and humans are sometimes thought to display neoteny as well.
But what does that mean for the strange gait of this apparently female insect? Well, it looks a bit like a regular adult insect, with a hard exoskeleton and all, but its general body shape is in fact that of a caterpillar. Caterpillars display complex gaits, not too surprising if you think about their body plan: six regular legs that will become the legs of the adult insect, a number of 'prolegs' (the knobby stumps further along a caterpillar's body), as well as final 'anal prolegs'. All of these are attached to a boneless body, providing endless opportunities of combining walking with stretching of the body. So that explains the trilobite beetle's walk: its' a caterpillar in disguise. Never underestimate insects' capability of oddness.
There is of course more to be told about caterpillar movement. In fact, at least in some species their gut moves inside their body before the outside follows up. The following video show that very nicely as well as the combination of body stretching with using legs. Perhaps there is a risk that you will learn more about caterpillar movement that you bargained for, but personally, I love details.