Actually, choosing an improving neighbor at random (the random edge pivot rule) also has expected exponential worst-case behavior, see Friedman, Hansen, Zwick, Subexponential lower bounds for randomized pivoting rules for solving linear programs.

More generally, it is not known whether a pivot rule exists whose (expected) worse case running time is polynomial.

For the shadow vertex rule, it has been shown that the smoothed complexity (i.e. after perturbation of the input) is polynomial. However, the shadow vertex rule is totally impractical.