Bem, finalmente resolvi. Percebi que a maioria dos aplicativos não tem um menu de contexto para os itens da barra de menus (clicar com o botão direito do mouse em uma opção de menu não faz nada) O Firefox, ao contrário, permite que você clique com o botão direito do mouse em um marcador e abra-o em uma nova guia, por exemplo.
Então eu criei um script apenas para o firefox, que muda seu usuário para outro usuário proxy, e depois executa o firefox com esse usuário. Eu precisava adicionar uma linha de comando para definir permissões em X para esse usuário.
O script que executa o firefox é:
xhost +local:
su - anotheruser
firefox
Dessa forma, ele solicitará uma senha, depois executará o firefox com esse usuário proxy.
Isso faz com que o Firefox permita que você clique com o botão direito do mouse em seus favoritos, tornando-o ótimo novamente!
EDITAR: Parece que meu firefox foi de alguma forma quebrado (não perfis, mas firefox) Instalar outro firefox em outro local, até mesmo a mesma versão, corrigiu meu problema de falta de menu)
Icecat funciona bem também
Outras versões do firefox (ou seja, mais antigas, mais recentes) também funcionam bem. Foi que meu firefox foi de alguma forma quebrado.