Casi lo has resuelto:
SELECT apellido,
nombre,
CAST(@s:= (CASE WHEN @s = 4 THEN 1 ELSE @s+1 END) AS UNSIGNED) AS '#'
FROM mitabla,
(SELECT @s:= 0) AS s
WHERE ciudad = "NEUQUEN"
and
ORDER BY apellido asc, nombre asc
Con (CASE WHEN @s = 4 THEN 1 ELSE @s+1 END)
reiniciamos el contador cada vez que llegamos a 4.