In this paper, we consider non-smooth convex optimization with a zeroth-order oracle corrupted by symmetric stochastic noise. Unlike the existing high-probability results requiring the noise to have bounded κ-th moment with κ ∈ (1, 2], our results allow even heavier noise with any κ > 0, e.g., the noise distribution can have unbounded expectation. Our convergence rates match the best-known ones for the case of the bounded variance, namely, to achieve function accuracy ε our methods with Lipschitz oracle require ˜O(d2ε−2) iterations for any κ > 0. We build the median gradient estimate with bounded second moment as the mini-batched median of the sampled gradient differences. We apply this technique to the stochastic multi-armed bandit problem with heavy-tailed distribution of rewards and achieve ˜O(√dT) regret. We demonstrate the performance of our zeroth-order and MAB algorithms for various κ ∈ (0, 2] on synthetic and real-world data. Our methods do not lose to SOTA approaches and dramatically outperform them for κ ≤ 1.