Я сказав би, що можна в цих випадках (усіх чи майже всіх) вжити "без усякого" - це однозначно ліпше за немилозвучне "без всякого". (Парадоксально, але факт: Караванський у своєму словнику синонімів наводить приклад "без всякого зла"). Але ж є й інші варіанти: без будь-якого, без жодного, без ніякого, без хоч би якого. Тому довгий перелік, де є лише "без всякого", викликає мимовільний протест
Не те, щоб "без усякого" було помилкою, -- не варто зациклюватися лише на цьому звороті, а ширше використовувати можливості мови.
Щодо сполуки з "сумнівом": є в АК такий зворот "понад уся́кий су́мнів". Вочевидь, можливий і "без усякого сумніву", хоча переважає, здається, "без жодного сумніву". У кожному разі, це германізм (ohne jeden Zweifel), що примандрував, можливо, через російську мову. (В. Сімович подає "народний" укр. відповідник - нічого й казати.)