innerHTML riscrive un codice dentro un oggetto.

Se tu usi sempre lo stesso oggetto, il tuo for continua a loopare (brutto neologismo) fino a che finisce, e quindi alla fine vedri solo il colore finale.

Nel tuo caso potresti preparati una tabella (tag <table> ) con tutti i posti e poi inserire i colori che vuoi,
oppure il document.write potrebbe andare bene.

Probabilmente una successione di 1000 document.write in successione manda in crisi il browser, ma prova cosi`:
codice:
var i=0;
var k=0;
var max=16; // fine loop
function Genera3(i,k) {
  for(var j=0; j<max; j++) {
    document.write("<div class='box' style='background-color: rgb("+Col[i]+","+Col[k]+","+Col[j]+")'>& nbsp;</div>"); 
  }
}

function Genera(i,k) {
  Genera3(i,k);
  k++;
  if(k>=max) {
    k=0; 
    i++;
    if(i>=max) return false;
  }
  var next = "Genera("+i+","+k+")";
  setTimeout(next, 500); // puoi abbassare un po' alla volta, se funziona
}
Attenzione ai colori che usi. I colori "web-safe" sono abbastanza pochi: ogni colore puo` avere circa 16 gradazioni.
Per l'accessibilita`, inoltre, i colori contigui devono essere sufficientemente separati in contrasto e luminosita`, con una formula che ora non ricordo a memoria, ma che posso cercare di recuperare, se serve.

Nota che la chiamta alla funzione Genera() deve essere fatta dal body, cosi`:

<body ...>
<div id="contenitore">
<script ...>Genera();</script>
</div>
...