Hey Sykarion,
One possible approach might be to create two objects for each on-screen character; a "Position" Sprite object that moves along the ground platform, and a "Graphic" Sprite object, that is pinned to the Position Sprite, but with a small randomized vertical offset. The Position Sprite would be made invisable in-game, so the player would only see the Graphic Sprite objects.
Finally, to make sure that the Graphic Sprites overlap each other correctly, (front to back), you just need to move each newly created Graphic Sprite to the correct Z-index relative to the other Graphic Sprites. To do this, you can re-sort them each time you create a new sprite, or you can move the new one to the correct Z-index on creation.
Both methods will amount to placing the Larger Y values (southward on screen) in front, and the smaller Y values (northward on screen) in back.