Layout HTML: adicionando coluna da barra lateral ao site existente

Eu tenho um site com um corpo que se parece com isso:

<body>
  <div id="header">...</div>
  <div id="content">...</div>
  <div id="footer">...</div>
</body>

Nenhum truque de posicionamento absoluto / relativo é usado nessesdivs, mas há muitosfloatsclearsmarginareiapaddings em estilos destesdivs e seus elementos internos. Tudo isso produz um site que se parece com isso:

┌───────────────┐
│     header    │
└───────────────┘
┌───────────────┐
│    content    │
└───────────────┘
┌───────────────┐
│     footer    │
└───────────────┘

A minha pergunta é: como eu adiciono uma coluna esquerda independente de largura fixa (barra lateral) com conteúdo extra que contrataria todo o site (cabeçalho-conteúdo-rodapé) e os mudaria para a direita.

┌────┐┌─────────┐
│side││ header  │
│bar │└─────────┘
│    │┌─────────┐
│    ││ content │
│    │└─────────┘
│    │┌─────────┐
│    ││ footer  │
└────┘└─────────┘

Eu sei de uma solução quase ideal, mas é feia e requer o re-aninhamento de divs existentes:

<body>
  <table>
    <tr>
      <td id="sidebar">...</td>
      <td>
        <div id="header">...</div>
        <div id="content">...</div>
        <div id="footer">...</div>
      </td>
    </tr>
  </table>
</body>

É possível fazê-lo com elegância, apenas adicionando um elemento da barra lateral externa em algum lugar do corpo, ou seja, assim?

<body>
  <div id="sidebar">...</div>
  <div id="header">...</div>
  <div id="content">...</div>
  <div id="footer">...</div>
</body>

Eu tentei abordagens ingênuas - como estilo:

#sidebar { float: left; width: 20em; }

ou

#header { margin-left: 20em; }
#content { margin-left: 20em; }
#footer { margin-left: 20em; }

Esse tipo de trabalho funciona, mas quebra logoclear: both&nbsp;ouclear: left&nbsp;é encontrado no cabeçalho / conteúdo / rodapé.

Então, existem alternativas para a solução de tabela?