eu servi o exercito em 1994 a 1995 sempre recebendo soldo abaixo do salario minimo, tem direito a alguma indenização trabalhista

não nem um centavo e se eventualmente tivesse vc não mais poderia pleitear nada pois ja decorreu mais de 05 anos, prazo máximo para propor qualquer ação contra estado municipio ou união.

Além do que existe esta Sumula Vinculante do STF que obriga tanto à Administração Pública como outras instancias do Judiciário abaixo do STF.
SÚMULA VINCULANTE 6 (Veja o Debate de Aprovação)
Não viola a Constituição o estabelecimento de remuneração inferior ao salário mínimo para as praças prestadoras de serviço militar inicial.
Ainda que ultrapassada a preliminar de mérito da prescrição a sumula obrigaria o juiz de primeiro grau a não conceder o pedido de diferenças de remuneração pagas em valores inferiores ao salário mínimo. Se conceder sob esta motivação de ser menor que o mínimo a remuneração o recurso de Reclamação nem passa pela segunda instancia do Judiciário. Sobe direto ao STF o processo para reformar a decisão.