Which one of OsCommerce, ZenCar and CubeCart is the easiest to customize with a custom design template? I know ZenCart is an offshoot of osCommerce so I'd guess they would be similar.
ZenCart and OSC are similar, but I would recommend Zencart over a standard OSC for template customization. I haven't used CubeCart.
If your modifications are only html/css customizations for one shop you should be fine with Zencart, although there are quite a lot of files to make a full template, with the modification of a few files on an already made template you will go a long way.
With the default template, I would suggest starting with:
Under the common folder: html_header.php, tpl_header.php, tpl_tabular_display.php, tpl_columnar_display.php, tpl_main_page.php and tpl_footer.php.
Sideboxes folder: the sideboxes you plan to use if you require html changes to them, perhaps you won't, with CSS you should be able to modify their appearance quite a lot.
Under the Templates folder: you will probably need to modify the html in the checkout pages, the product_info_display page and the half a dozen listing pages.
You don't mention Prestashop. It is a much more modern software than Zencart or OSC (code wise), completely written with OOP and, more importantly, it uses Smarty for its easy to follow template system.