E-commerce and free don't really go hand in hand. Premium themes will have way more functionality and customisation than a free alternative and when you're dealing with payment gateways there will be some cost involved somewhere. That being said you could buy all the bits you need for a woocommerce site for around £150 (that's buying the bits, not paying for a developers expertise putting them together).
Something to consider with an e-com site is how bigger store you're looking to build? I've found that woocommerce is great for up to 20 basic products but over that, you should be looking at magento.
I'd contest that really heavily. There's an awful lot of sites using WooCommerce successfully for huge projects. I've just used it to build a ski rental website, with hundreds of variables and products. It's a fantastic bit of software. EDIT: Though you do need some PHP knowledge/extensions to get the very best from it.
In regards to themes, try WooThemes, or, Themeforest and look out for WooCommerce integration.
Essentially Woocommerce and Magento share pretty much the same core functionality. However as a store becomes bigger, the store owners need a greater level of management over the products within that store and the woo reporting system just isn't as good as a dedicated e-commerce solution such as Magento.
Another area, not so much related to a large catalogue but certainly a consideration for businesses who intend trading outside their base currency is woocommerce's lack of multi-currency support. If I want to sell a product in 3 or 4 different currencies using woo, I have to buy a plugin, which at checkout defaults back to the base currency. Seemingly the only way round that issue is to run multiple installs, which is never going to work very well long term.
Something else that gets on my tits with woo is its bloody silly product filtering which is nigh on impossible to alter with any real success. Even premium plugins don't seem to stop woo's love affair with 'newness'.
All that having been said, I've taken on 2 new Woocommerce projects in the last 24 hours. lol