Mudar o HTML padrão do menu

Olá pessoal,

Estou com um pequeno problema e, buscando no codex (http://bit.ly/nav-codex), não consegui achar a solução. Quero fazer um menu na seguinte estrutura:

<li>
    <span></span>
    <a href="javascript:void(0);">História</a>
</li>

Já habilitei o menu no tema, já está aparecendo normalmente no lugar que quero, porém o HTML fica da seguinte maneira:

<li>
    <a href="javascript:void(0);">História</a>
</li>

Como faço pra inserir esse <span> antes do ? Já tentei usar o before, mas quando coloco o menu nem aparece. Vi algo sobre o ‘walker’, porém não entendi muito bem a funcionalidade.

Fico no aguardo.
Valeeu