Exotic spin-dependent interactions between fermions have recently attracted attention in relation to theories beyond the Standard Model of particle physics. The exotic interactions can be mediated by new fundamental spin-0 or spin-1 bosons which may explain several important unsolved mysteries in physics, such as the existence of dark matter in the Universe. In this study we expand this area of research by probing an exotic parity-odd spin- and velocity-dependent interaction between the axial-vector electron coupling and the vector nucleon coupling for polarized electrons, which has not been well explored. This experiment utilizes a highly sensitive atomic magnetometer, based on an optically polarized rubidium vapor, which is both a source of polarized electrons and a magnetic-field sensor, and a solid-state test mass containing a high density of unpolarized nucleons. By linearly moving the test mass with a constant velocity next to the rubidium vapor, an exotic interaction between the unpolarized nucleons and the polarized electrons can induce an effective magnetic field, which can be detected by the atomic magnetometer. We set an experimental limit on the electron-nucleon coupling strength of \(10^{-30}\) at the interaction range above \(10^{-3}\)~m, corresponding to the mediator boson mass less than \(10^{-4}\)~eV. This result significantly improves the constraint for the electron-nucleon coupling strength by up to 17 orders of magnitude beyond the current limit.