This took me a while to find.
We can't use
THEME_menu_link() because it has no count and no context
THEME_menu_tree() because the child items are already rendered into HTML
THEME_preprocess_menu_tree() also only has the rendered children available
There didn't seem to be any drupal_alter I could intercept between when the menu array was built menu_tree_output() and when it was sent for rendering (eg menu_block_view()
Eventually I found that I could get at the raw list of links early enough with THEME_preprocess_menu_block_wrapper() and insert the appropriate attributes into the render array there.
* Preprocesses menus being rendered in blocks to add zebra-striping classes to
* each menu item.
* Desired output has odd/even classes like: