Mit einer Tabelle ist es einfach, aber geht es ach mit <div> elementen und css?
Ja, auch mit <div />-Elementen und CSS ist das kein Problem, allerdings werden dir einige ältere Browser einen Strich durch die Rechnung machen.
Es liegt aber die Vermutung nahe, dass es sich bei äußeren, flexiblen Spalten um "Designelemente" handelt und nicht um Inhaltsspalten. In diesem Falle wäre es Grundsätzlich anzuraten, die Struktur zu überdenken und keine "Spalten" zu bauen sondern nur zu tun als ob - z.B. mit 2 verschiedenen, Hintergrundbildern in <body /> und <html /> (1x links und 1x rechtsbündig)