Bom, antes de mostrar como fazer com Velocity, o seu codigo JSP ficaria muito mais legivel se fosse feito assim:
<%
Vector vNac = new Vector();
oNac.setAcationNac("findNacionalidade");
oNac.execActionNac();
vNac = oNac.getID_Pais();
int size = vNac.size();
int divize = size / 2;
String[] ID_Nacionalidade = new String[divize];
String Pais[] = new String[divize];
%>
<select name="Nacionalidade" onchange="setarNacionalidade()">
<option value="none">Escolha um Pais</option>
<%
for(int i = 0; i < size; i++) {
ID_Nacionalidade[0] = (String)vNac.get(i);
i++;
Pais[0] = (String)vNac.get(i);
%>
<option value="<%= ID_Nacionalidade[0]%>"><%= Pais[0]%></option>
<%
}
%>
ps: achei meio estranho vc criar um array de size / 2 tamanho mas sempre atribuir os dados a posicao 0 no array…
Bom, indo pro assunto principal, para fazer isso com Velocity vc tera que mudar o codigo Java para um arquivo .java, o qual ira executar as acoes de encontrar a nacionalidade etc etc… entao, ao inves de fazer um loop como vc fez, vc primeiro coloca em um ArrayList e entao configura esse ArrayList em um contexto visivel ao Velocity, e depois eh so usar as tags da VTL ( Velocity Template Language - tem um tutorial aqui no guj sobre isso ) para mostrar os dados.
Como nao entendi mto bem o teu exemplo, vou mostrar com um outro codigo bem simples de entender: pegamos do banco de dados a relacao de nomes dos empregados de uma empresa, e entao fazer um template para mostrar esses nomes em um <select>.
Se fossemos fazer em JSP ficaria mais ou menos assim:
<%
...
// executar aqui o codigo sql para pegar os empregados
// fazer o loop e ir mostrando na tela os nomes
%>
<select name='empregados'>");
<%
String nome = "";
while (rs.next()) {
nome = rs.getString("nome_empregado");
%><option value="<%= nome>"><%= nome%></option><%
}
%>
</select>
<%
// resto do codigo etc etcc
%>
Para fazer isso com Velocity, movemos o codigo java para um arquivo .java, o qual ira se encarregar se processar tudo e colocar em um ambiente visivel ao velocity. Se fosse um ambiente real de producao e se quisessemos seguir corretamente as regras de Design Patterns, o exemplo aqui teria que ser mais separado as camadas ainda, mas para fins didaticos nao eh necessario tamanha abstracao :).
Basicamente o que precisamos fazer eh isso:
// AlgumArquivo.java
....
// executar aqui o codigo sql para pegar os empregados
// Pega os dados e coloca em um ArrayList
ArrayList listEmpregados = new ArrayList();
while (rs.next())
listEmpregados.add(rs.getString("nome_empregado"));
...
// Cria o contexto do Velocity para colocarmos os dados
VelocityContext context = new VelocityContext();
context.put("empregados", listEmpregados);
// Faz outras acoes necessarias para o Velocity
// codigo codigo codigo
ps: o codigo acima ( o que cria o contexto do velocity ) na maior parte das
vezes vai ser um Servlet.
Bom, com isso ja tiramos o codigo Java da camada de apresentacao, agora precisamos montar o template para mostrar os dados na tela:
## mostraEmpregados.html
## Apesar da extensao .html, este eh um
## arquivo com diretivas VTL
## Monta o <select> dos empregados
<select name="empregados">
#foreach ($nome in $empregados)
<option>$nome</option>
#end
</select>
e pronto!!! Viu como a parte de montar o layout ficou super simples e sem uma unica linha de java dentro?! 
Bom, basicamente eh isso. Apesar de dar mais trabalho na hora de programar, ja que eh preciso pensar melhor como o codigo vai ser feito, precisa fazer os .java e o Servlet, a medio/longo prazo compensa mto, pois a manutencao do sistema fica muito mais facil e simples.
Sei que o exepmlo fico meio grande e nao mostrou codigos concretos, mas eh que ficaria inviavel postar tudo no topico. Como voce ja deve ter visto, ja entrou um tutorial sobre a VTL, e na semana que vem ja estara entrando mais um tutorial de Velocity, o qual ira mostrar - e explicar - exemplos de aplicacoes usando Servlets e XML com Velocity. Portanto, caso nao tenha entendido tudo, ja esta vindo um tutorial ai 
Rafael