There are a few possibilities to solve this.
The first one, with taxonomies (categories), is not very usable because of the interface to set the category for the accomodation. Additionally, you will have a lot of duplicate categories, as every city will need a subcategory like hotel, b&b, ... Because of this the Searchfunctionality for the categories becomes useless.
The second one, creating it all with pages, is quite okay. You will have a few issues here, as the pages for country, accomodationtype etc. will have different types of content to show. For the Admin Panel using Admin Collapse Subpages could solve the issue of having a enddless list of pages.
The third one, using custom post types, also has a few difficulties. You will have to create custom meta boxes to set the accomodation to an accomodation type to a city etc. Using a Plugin like hierarchy could solve you this issue.
I created something similar for a client of mine (check it here), and i opted for another solution: creating custom rewrite rules for a custom post type (accomodations), setting up the region, type etc.
The thing i did different from you is that the regions and cities are not accessible through the same URL-structure, but have pages dedicated to them. The client has to put the SEO-Texts into Pages, and I list all the accomodations for the given criteria specified in the page below the Page content.
So in my case, a URL for a accomodation would be
http://www.unterkunft-tirol.at/unterkunft/hotel/paznaun-ischgl/galtuer/hotel-garni-versail/, but if you leave the slug for the accomodation away (hotel-garni-versail), the url
http://www.unterkunft-tirol.at/unterkunft/hotel/paznaun-ischgl/galtuer/ does not show any results. The author has to create a page for that region, where he can promote the specific region. This would be something like
http://www.unterkunft-tirol.at/zillertal/, where he can write the text as page content, and a listing of all the accomodations to this criteria below.
you could of course rewrite the urls for the regions as well, but you have to use other post types than the one for the accommodation.
Hope this gives you an overview about your possibilities, and the pro and contra of each.