1) So you are asking for a database schema that will handle variations in addreses from country to country? I'm not the one to answer that as I haven't looked into what all of the variations are. Though something like Name, AddressLine1, AddressLine2, AddressLine3, City, State/Region, Country, PostalCode might do. Check out some open source apps that already gather this type of information (SugarCRM comes to mind) for ideas.
2) You need a *-ds.xml file to define the datasource to the webservice. That's about it.