No, your phone would not need to be unlocked. And you would never find one for "cheap" anyways. The reason carriers are able to offer cell phones for less than a couple hundred bucks, is because they're locked to the carrier you got it from. This means the phone is useless if you don't pay the bill, and they'll just cut their losses and move on. Buying an unlocked phone on the other hand, typically requires the purchase to be done directly from the device manufacturer. Or from a third party who specializes in retailing unlocked devices. Either way though, without the carrier lock, the device will not be subsidized, and you will pay full price.
As was suggested above, Google Voice, is likely the best option. It's free, and it just works. There are other options available though. Once you get your phone just search Play Store for "voip" and see what comes up. VOIP stands for "voice over internet protocol."