PythonでExcelファイル（BIFF形式、拡張子でいえばxls）を扱う場合には、

• pyExcelerator
• xlrd, xlwt, xlutils
• Win32OLE（Windows環境のみ）

辺りを使うのが一般的かと思います。他の選択肢は知りません。
今回は開発環境がMac OS X 10.6、デプロイ環境がCentOS 5.4だったので当然Win32OLEの選択肢は除外しました。
pyExceleratorは、罫線やフォントやセルのスタイルなどのデータを細かく指定して書き出せるようですが、読み込み機能が凄くシンプルで、セルの値とその座標のみ抽出できる（罫線やフォントやセルのスタイルなどは読み込めない）ようで、「装飾を施して体裁を整えたExcelファイルを読み込む」→「必要な部分だけ上書きして保存」といういわゆるテンプレート方式のExcelファイルの利用ができません。（まぁ、かなりのコード数を利用側で費やせば不可能ではないと思いますが、それってPythonでExcelファイルを扱うモジュールを自作するようなもので・・・）

xlrd, xlwt, xlutils（多分それぞれExcel Read, Excel Write, Excel Utilitiesの略かな？）も、モジュールが別になってる事から分かる通り、読み込みと書き込みが別になってるのですが、xlutilsを使うことである程度連携させることができます。
具体的には、

from xlrd import open_workbook
from xlutils.copy import copy

rb = open_workbook('test.xls', formatting_info=True)
wb = copy(rb)
wb.save('test2.xls')

とすれば、test.xlsの体裁を保ったままtest2.xlsに保存する事ができます。
ミソはformatting_info=Trueで、これを指定するとxlrdがセルのスタイル情報も読み込んでくれて、xlutils.copyがちゃんとxlwtにコピーしてくれます。（ただ、ページ設定等はコピーされないようです。）

で、wb.saveの前にwb（xlwt.Workbookクラスのインスタンス）のget_sheetメソッドを使ってxlwt.Worksheetクラスのインスタンスを取得し、そのwriteメソッドなどを使って必要なデータを上書きすれば目的達成！となるはずですが、実際にやってみると上書きしたセルのスタイル情報がクリアされてしまうという問題が起きます。

そこで、Worksheetクラスのwriteメソッドの引数定義を見ると

def write(self, r, c, label='', style=Style.default_style):

となっていて、styleを指定しない場合にはデフォルト値（スタイルなしだと思われる）で上書きされるようになってます。
styleにxlwt.Styleクラスのインスタンスを渡せば良さそうですが、xlrdからスタイルを読み込んでこのメソッドのstyleに渡してもクラスが違うとかでエラーになります。
xlwtとxlrdのファイル構成を見ると分かるのですが、かなりクラスの構成が違うようで、xlwtのstyleとxlrtのstyleはダックタイピングには対応してないようです。

じゃあ、xlrdじゃなくてxlwt自体から元のstyleを取り出してwriteメソッドの引数に渡してやればいいんじゃないか？xlutils.copyでスタイル情報もコピーされてるんでしょ？と思いますが、ソースを見るとxlwt.Styleクラスのインスタンスは即座にインデックス（単なる数値）に変換されてそのインデックスが保持されるようになっていて、xlwt.Styleクラスのインスタンスはどこにも保持されてないように見えました。
さらにインデックスからxlwt.Styleに逆変換するのも難しい感じでした。（BIFF形式に詳しければ不可能ではないと思います）

まぁ、正直言うとxlrdのスタイル情報から属性を全部読み取ってxlwt.Styleクラスのインスタンスを生成してwriteメソッドに渡すコードを書けばいいだけですが、スタイルの属性も多岐にわたっててなんかめんどくさそうだったのと、writeメソッドの仕様的にstyleを指定しなかったら元のスタイルを保持するほうが美しくね？と思ったのでその方向で行くことにしました。

ソースを読むとxlwt.Worksheet.writeメソッドは最終的にxlwt.Row.insert_cellメソッドを実行するようになっています。
そう、メソッド名から分かるとおり上書きだろうが常にcell（xlwt.Cellクラスのインスタンス）を追加するようになっています。
セルの値は単純な数値以外のデータ（文字列など）もスタイルと同じようにインデックスに変換されて保持されていて、この
insert_cellメソッド内で、元のセルの値のインデックスを削除して新しいセルを追加するという処理が行われています。
ここで、元のセルのスタイルのインデックスを新しいセルに設定してやればうまく行きそうだという事が分かります。

実際にはxlwt.Row.insert_cellを以下のように書き換えました。（xlwt 0.7.2  Row.py）

def insert_cell(self, col_index, cell_obj):
    if col_index in self.__cells:
        if not self.__parent._cell_overwrite_ok:
            msg = 'Attempt to overwrite cell: sheetname=%r rowx=%d colx=%d' \
                % (self.__parent.name, self.__idx, col_index)
            raise Exception(msg)
        prev_cell_obj = self.__cells[col_index]
        cell_obj.xf_idx = prev_cell_obj.xf_idx
        sst_idx = getattr(prev_cell_obj, 'sst_idx', None)
        if sst_idx is not None:
            self.__parent_wb.del_str(sst_idx)
    self.__cells[col_index] = cell_obj

”cell_obj.xf_idx = prev_cell_obj.xf_idx”の行を追加しただけです。
cellのxf_idxにスタイルのインデックスが入ってるのでそれを元のセルから新しいセルにコピーしただけですね。
本当はsst_idx（単純な数値以外のデータのインデックス）と同じようにgetattrとか使った方がいいのかもしれませんが、xlwtの〜Cellクラスにはすべてxf_idxが定義されてるようでしたので。

site_packagesに入ってるソースを直接書き換えたり、インストール前に書き換えてからsetup.py installしてもいいのですが、ライブラリを直接変更するのもあれだし、このままだと逆にxlwt.Worksheet.writeメソッドに独自に指定したstyleが無視されてしまうし、他に不具合があるかもしれないので、実際は継承するなりして修正点を反映するほうがよろしいかと思います。
今回はxlwtのクラス全体的にわたる別の機能追加も行いたかったので、継承はせずにxlwtの各クラスにメソッドを追加するモジュールを書きました。

あとは、ページ設定などが反映されない問題は、wsにxlwt.Worksheetのインスタンスが入ってるとして

ws.top_margin = 3.0 / 2.54    # 1インチは2.54cm
ws.left_margin = 1.5 / 2.54    # 1インチは2.54cm
ws.right_margin = 1.5 / 2.54    # 1インチは2.54cm
ws.header_str = ''
ws.footer_str = ''
ws.fit_num_pages = 1

なんて感じで、余白とヘッダ・フッタ、収めたいページ数なんかを指定するとだいだいの要望は満たせるかと。
用紙のサイズなんかも他のプロパティで設定できるようです。（デフォルトはA4サイズっぽい）