you can have voluntary, free trade without government. whether it's called "capitalism" or something else can be a matter of discussion...
If all free trade actions could be resolved by rational, respectful, interaction of two individuals of integrity (ie they keep their word), then no government is needed. As far as I can tell, if such a world existed, we wouldn't be having this discussion.
As long as individuals need to collaborate in order to resolve disagreements, as long as certain individuals need to take responsibilities for overseeing these collaborations, government is necessary.
the assumption that warlords would always appear in society no matter what is just that - an assumption. on the other hand, every government we have today was born by conquest and initially created by warlords.
I simply don't hold to the assumption that government will always be necessary in society to protect property rights. they are actually the biggest violators we have of property rights. people are capable of progressing beyond government, and I think they will once they finally realize what government really is.