I'm not sure why you wouldn't be able to do this with woo-commerce. It supports both...
I have worked with several wordpress carts: The Shopping Cart Plugin from Tribulant, wp e-commerce, e-shop and woocommerce.
Tribulants software is a one time fee per site (with a yearly fee if you want new updates). The upside is that several payment and shipping options are already included and free... and it integrates with most themes. The downside is that if you need something special, they will need to custom program it for you.
Woocommerce has just about any extension that you might want to add later so for that reason that is now my preferred e-commerce plugin. The downside is that you have to pay for all these plugins. But of course they have to make money somehow. I found a website (gplclub.org), that will let you download almost all woocommerce extensions for a yearly fee which is about as much as paying for a UPS and Paypal Advanced plugin (so it's well worth it).
Woocommerce has integration documentation, so you can adapt your theme to go with it but sometimes you will have to do quite some styling if it wasn't integrated with it. I would however recommend using a theme that is compatible just to take out some of the hassle.
If you can't find a theme you like that is woocommerce friendly, check out the Ultimatum theme builder. It pretty much lets you build whatever you want and it integrates with woocommerce.
The problem with Magento and other solid e-commerce frameworks is that they all look so boring, I think.
I would caution you to use a theme with it's own proprietary integrated e-commerce function, because if the theme developer decides to not support it anymore, you have to start over (it happened to two clients of mine).