Versions web service is no use in your case. You need to use Lists web service (http:///_vti_bin/lists.asmx) and Lists.GetVersionCollection Method
Returns version information for the specified field in a
So you need to query field by field and as far as I know there is no method to return all field versions at once.
Your code could look something like this:
WSLists.Lists listService = new WSLists.Lists();
listService.UseDefaultCredentials = true;
XmlNode result = listService.GetVersionCollection(
"xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx", "[ITEM ID]", "[FIELD NAME]");
string outerXml = result.OuterXml;
and outerXML looks something like this:
<Version [FIELDNAME]="[VALUE]" Modified="[TIMESTAMP]" Editor="[USER]" />
I never used this approach but I did some tests (on SP 2010 - but I don't think there is difference). I never found good way to easily get all fields for all versions.
And Client Object Model is SP 2010 feature only but except of FileVersion Class I don't see anything similar to 'Get me item versions with metadata'.