Solution: First, we prove that $n = 6$ satisfies the condition. Let $P_1, P_2, \dots, P_6$ be the vertices of a regular hexagon in consecutive order. Let $A_1 = P_1, A_2 = P_3, A_3 = P_5, A_4 = P_2, A_5 = P_6, A_6 = P_4$. Then, these 6 points satisfy the conditions. See the figure below.

We now prove that $n \le 5$ does not satisfy the given conditions. Clearly, $n = 3$ does not satisfy the condition because for any $1 \le i \le n, 1 \le j \le n$ in the statement, we require $j - i \ne -1, 0, 1 \pmod{n}$.

When $n = 4$, if $A_1, A_2, A_3, A_4$ satisfy the conditions, then $A_1A_2$ and $A_3A_4$ must bisect each other, and $A_2A_3$ and $A_4A_1$ must bisect each other, which is impossible.

Therefore, we only need to consider the case when $n = 5$. Suppose $A_1, A_2, A_3, A_4, A_5$ satisfy the conditions. For any $1 \le i \le 5$, we require $j \equiv i + 2, i + 3 \pmod{5}$ in the statement. We consider two cases.

Case 1: Two of the line segments $A_iA_{i+1}$, $i = 1, 2, 3, 4, 5$ bisect each other. By symmetry, we assume that $A_1A_2$ and $A_3A_4$ bisect each other. Note that applying an affine transformation to the plane does not affect the conclusion, we can assume that $A_1A_2$ and $A_3A_4$ are perpendicular bisectors and have equal length. Let $O$ be their intersection point, and let us establish a Cartesian coordinate system with $O$ as the origin. Let $A_1(0, -2), A_2(0, 2), A_3(2, 0), A_4(-2, 0)$. Then the midpoint $M$ of $A_2A_3$ must lie on either $A_4A_5$ or $A_1A_5$. Without loss of generality, we assume that $M$ lies on $A_1A_5$. Note that the slope of $A_1M$ is 3, so we can assume that the coordinates of $A_5$ are $(1 + x, 1 + 3x)$, where $x > 0$. See the figure below.

Now consider the midpoint $N$ of $A_4A_5$. If it lies inside the segment $A_1A_2$, then $1+x+(-2) = 0$ implies $x = 1$. However, in this case $A_4, A_2, A_5$ are collinear, a contradiction. If $N$ lies inside the segment $A_2A_3$, then
$$\frac{1+x+(-2)}{2} + \frac{1+3x}{2} = 2,$$
also yields $x = 1$, which is a contradiction.

Case 2: None of the segments $A_iA_{i+1}$, $i = 1, 2, 3, 4, 5$ bisect each other. Without loss of generality, assume that the midpoint $B_1$ of $A_1A_2$ lies on $A_3A_4$. Then the midpoint $B_3$ of $A_3A_4$ lies on $A_5A_1$, the midpoint $B_5$ of $A_5A_1$ lies on $A_2A_3$, the midpoint $B_2$ of $A_2A_3$ lies on $A_4A_5$, and the midpoint $B_4$ of $A_4A_5$ lies on $A_1A_2$. This implies that connecting $A_1, A_2, A_3, A_4, A_5$ in sequence yields a five-pointed star.

By the Law of Sines,
$$1 = \prod_{i=1}^{5} \frac{\sin \angle A_i B_i B_{i+2}}{\sin \angle A_i B_{i+2} B_i} = \prod_{i=1}^{5} \frac{A_i B_{i+2}}{A_i B_i} = \prod_{i=1}^{5} \frac{A_{i+1} B_{i+3}}{A_i B_i} < \prod_{i=1}^{5} \frac{A_{i+1} B_i}{A_i B_i} = 1,$$
where the subscripts are understood modulo 5. This is a contradiction.

Therefore, the minimum $n$ we seek is 6.