A melhor maneira é fazeres guest posting em sites populares. Tens logo acesso a uma grande audiência e quem clicar no teu blog tem grandes hipóteses de ser tornar um leitor regular (porque o tráfego é targeted).
Infelizmente, Portugal é um país pequeno e os sites de qualidade contam-se pelos os dedos. Se o teu site fosse em inglês tinhas uma audiência de centenas de milhões.
Existem bloggers que têm tido sucesso com o Youtube. Fazem filmes, metem um intro e outro com um link para o site e done.
Existe uma minoria de bloggers que não têm de mexer uma pallha porque os motores de busca fazem tudo por eles. Mas esses criam algo que as pessoas gostem e mais ninguém tenha.
Podes sempre ir offline, mandar fazer uns panfletos e distribuir em sítios como escolas.
Outra coisa que parece resultar é criares concursos onde ofereçes coisas com o logo do site (t-shirts).
Agora o que recomendo é focares na tua audiência. Não percas tempo a tentar a chamar atenção de pessoas que sabes que não vão gostar do teu site.
Boa sorte.
