A mio avviso l'unica soluzione è quella di usare un min-height al 100% per il box che contiene l'header e le due colonne:
http://www.alistapart.com/articles/footers/

Potresti poi usare un'immagine che dia lo sfondo alle due colonne simulando l'efetto dell'allungamento di una all'allungarsi dell'altra:
http://www.alistapart.com/articles/fauxcolumns/

Attenzione che queste due soluzioni simulano l'effetto che vuoi ottenere in quanto che io sappia, a meno che tu non stia usando le tabelle, non è possibile fare altrimenti.