For lower zoom levels, I decided to take the NASA Blue Marble as tile source.
The original is downloadable here: http://visibleearth.nasa.gov/view.php?id=57752
For zoom levels 0 to 4, I took the small one and made the tiles with gdal2tiles:
gdal2tiles --s_srs EPSG:4326 --zoom 0-4 D:\Karten\Geotiff\BlueMarble\bluemarble.tif D:\Tiles\test
Fro zoom level 5 to 7, I took the high-resolution of half the world:
gdal2tiles --s_srs EPSG:4326 --zoom 5-7 D:\Karten\Geotiff\BlueMarble\bluemarble-ost.tif D:\Tiles\test
Gdal2tiles needs a little patch to use the OSM-like tile naming. I described the workflow here: GDAL2Tiles: MapTiles from BSB/KAP are Switched
You only have to do that once, as the world does not change much looking at low zoom levels.
My OSM tiles built with Mapnik start at zoom level 8. This can be defined in generate_tiles.py
To save disk space, I wrote a little recursive batch file to delete empty tiles:
for /R .\ %%N IN (*.PNG) DO if %%~zN LSS 120 del %%N
This works for Windows, you have to test which file size in bytes is best for you.
EDIT
Another choice is to set up a bunch of bounding boxes covering the coastlines in a better way than one single bounding box does. This will save creation time as well.