Look for a template-driven cart system, maybe? I've been using EZShopper, and I'm pretty sure as long as you coded the product pages or search result templates properly, you could use almost any type of form input with it. Drawback: having it set up to work with an instant payment processing gateway (like AuthorizeNet, etc.) will cost extra.
I've helped to develop many sites using Americart, and find their flexibility and portability to be excellent.
They support all kinds of options to modify an item (checklist, select lists, radio buttons - up to 44 per item). In fact, over the five years I've been using them (and they've been around longer than that) they've only grown more flexible. I only once had a client ask for a feature that their service couldn't support, and they added that feature. They include support for multiple shipping methods, database input for thousands of items and a seamless interface to many major payment processing services, such as AuthorizeNet, Linkpoint, IBill, Verisign, PayPal, etc.