This all works in evil-mode as well, and by default you get the cool live-preview (not sure how to enable that for the vanilla C-M-%)
:%s/\([0-9]+\))/\,(1- \#1))/
will turn 1) one
2) two
3) three
into 0) one
1) two
2) three