Удаление определенного className у всех узлов. Производительное решение?
А обязательно именно удалять классы? Может, достаточно их просто отключать?
Если да, то можно сделать так:<body class="your-class-enabled">
  ...
    <div class="your-class">...</div>
    <div class="your-class">...</div>
  ...
</body>
И CSS переделать. Вместо.your-class {
  ...
}
писать.your-class-enabled .your-class {
  ...
}
В этом случае достаточно убрать класс "your-class-enabled" из body и класс "your-class" отключится у всех элементов разом.
Если браузер поддерживает document.getElementsByClassName, то делаем один раз выборку, получаем "живую" коллекцию и работаем с ней jsfiddle.net/tBASB
Либо как советует lorus, быстро и красиво.