Woocommerce can be integrated into other themes. There are some instructions in the codex on their website as to how to do this. Many of the functions are available as shortcodes so it isn't necessary to use a Wootheme, it is just easier.
One of the things that you will want to do is sort out what features you absolutely need. If you are looking for a free solution then you are likely going to need something with the large user-base of WP-ecommerce. Woocommerce has the advantage of being the new guy on the block so has been written more recently. It doesn't have the same user base to have to provide historical support to, but the downside is that there are less users and things like payment gateways or shipping modules to allow for customisation.
I went through an extensive search of ecommerce platforms for a website a few months ago but had to count out many on the shipping modules. They weren't complex enough or easily customisable enough to work outside of the US (and not using integrated shipping like FedEx etc). I ended up setting up Woocommerce to work with my theme and using the Shipping Table module as a bought addon. Another I set up slightly later was able to utilise a newly published plugin from Codecanyon that worked with the NZ Post API for a purchase of a few dollars. Both these situations allowed for me to stay using a free ecommerce solution and tailor them with minimal money to the websites need.