Precisas de uma licenciatura no mínimo com 120 ECTS em UCs da área científica de História para ingressares num mestrado em Ensino de 3° ciclo e Ensino Secundário. Os professores de 1° e 2° ciclo precisam de licenciatura em Educação Básica. O mestrado é bastante relevante porque se apenas tiveres uma licenciatura só podes concorrer em concursos locais de escolas que tenham falta de professores e com a legislação actual não podes pertencer aos quadros de escola - ou seja, se só planeares uma licenciatura, provavelmente vais ter mais instabilidade que uma pessoa que tire um mestrado. Dito isto, é mesmo recomendável que escolhas uma licenciatura que te permita o acesso ao mestrado, portanto, ires para História da FLUP seria o ideal. Poderias fazer os créditos "avulso" como sugeres, mas seria muito mais caro do que simplesmente mudares de curso. Podes concorrer novamente pelo concurso nacional e podes também no final deste ano lectivo tentar pelo concurso mudança par instituição/curso. Concorreres aos dois dá-te duas hipóteses de conseguires entrar no curso, o que a meu ver é positivo. Se achares que a tua média está muito distante para conseguires por qualquer um destes cursos, é recomendável nessa situação que repitas provas de ingresso/faças melhoria de notas do secundário. Alguma dúvida, dispõe!
Caso te refiras ao Ensino Superior, a contratação é feita por concursos locais das universidades e tens de ter um Doutoramento na área de História. Se há gente que começa a dar aulas antes? Sim, mas tal como no Ensino obrigatório para realmente pertenceres à carreira tens de ter o grau solicitado, o que te dá mais estabilidade e é mais vantajoso. Para este percurso, até poderias vir de uma licenciatura em Arqueologia e depois um mestrado e doutoramento em História, mas se não estás a gostar do curso, mais vale investires em mudar do que insistir num curso "para não perderes 1 ano". Espero que ajude!