4 months in Europe

The only thing that you will really need to schedule is time outside the Schengen Zone, where you may only spend 90 days out of any 180. The Schengen Zone includes most of Europe, and the 90 day limit is for the whole zone, not individual countries. As long as you take care of that, there is nothing particularly difficult with moving as you please and making decisions on the fly. I would probably consider where I wanted to go and in what order, and then make sure that there was nothing in that area that might impact your ability to find housing (festivals and holidays, school breaks).

I posted at the same time as Nancy.
The Schengen rules limit those with a US passport to 90 days total in all European countries (about 25) that are covered by the Schengen rules. There are some exceptions--but it's critical in your planning that you determine that you're within one of the exceptions, because the penalties for over-staying the 90 days can be significant.
You can use the Search function (above) to find several recent discussions of the Schengen rules.

Well, the first thing to be carefully planned is how are you going, depending on your nationality, to cope with visas. Most European countries - but not all - have a common system of visas named Schengen, and people from most countries of the world can easily stay 90 days out of any 180 consecutive days in the Schengen area - either by getting a relatively easy tourist visa, or even without a visa (for example if you are from US). Staying longer in the Schengen area is a harder nut to crack, but by planning some stays out of the area (for example in UK) you can keep within the 90 days limit. But it is a thing that should better be planned in advance.

Nobody can make you any guarantees. If you'll have a rental car, it makes it easier to follow your own schedule and to reach more lodging that is not convenient to train stations. But it's expensive to pick up a car in one country and drop it in another. Also, a car will do you no good in the major cities where you pay for parking. For those big cities, hotels, train tickets, or airline tickets are all likely to be cheaper and offer more options if booked in advance.

If reserving on short notice, you're more likely to pay full fare for train tickets and to have a limited hotel selection, although the big cities do have plenty of hotels. The issue is not necessarily that everything will sell out. August is a busy month for tourism, but the big cities you have in mind aren't the most popular August destination for Europeans, who flock to the beaches.

There have been several well-discussed threads in this forum recently on the topic of flexibility, if you can poke around to find them. Some are under Scotland and Ireland assume using a car.

Of course, if you're visiting as a tourist, your stay is limited to 90 days within the region that uses the Schengen Visa. Britain and Ireland are separate from that, so you might spend on of your months in that area. See http://www.ricksteves.com/travel-tips/trip-planning/travel-documents.

4 months / 16 weeks / 16 cities. Give yourself a sketched out plan as a framework. Perhaps lock in your first 2 or 3 weeks during the summer peak, then maybe book each stay 3 weeks ahead. So for something like my suggestion below, book Berlin whilst you are in London....
London
Paris
Amsterdam
Berlin
Prague
Vienna
Budapest
Munich
Switzerland
Venice
Rome
Florence
Cote d'Azur
Barcelona
Madrid
Lisbon

Thanks for the great information. I was not aware of the Schengen rules. I guess that is why I am starting this planning process now.

Glad we could help.
You can use the Search function (above) to search on Schengen, you'll get a quick education on what you need to know about this potentially complicated subject.

If you don't have an EU passport and have to comply with the 90 day (nearly 13 weeks) maximum for a Schengen tourist stay then consider Scotland, Croatia and Turkey. Note this 90 days is a maximum total within a 6 month period. You don't get another 90 days simply by leaving and re-entering.
Scotland (non Schengen)
London (non Schengen)
Paris
Amsterdam
Berlin
Prague
Vienna
Budapest or Munich
Switzerland
Venice
Rome
Florence
Cote d'Azur
Barcelona
Madrid
Dubrovnik (non Schengen)
Istanbul (non Schengen)

If you have four months and you aren’t really picky about what you do then I guess it’s great. If it were me I might want to check special events or once in a lifetime opportunities that I would want to take advantage of while in Europe. There are a number of web sites and publications about the world’s greatest festivals and events. If you stay in apartments you will find them available without much notice so that works.

Well everyone hit you with the Schengen zone. Your plans to start in “the North” and end in Spain means you are either going to make a big circle or you are not going to go too far.

The UK isn’t in the Schengen zone so it will help to stay there for a while. Other countries that are not in the zone are (always confirm for yourself please):
Romania http://uk.lsrs.ro/files/Sibiu-Romania.jpg
Bulgaria http://www.traveltop.net/wp-content/uploads/2012/05/historic-plovdiv-bulgaria.jpg
Croatia http://www.greecemedtravel.com.au/filelibrary/images/Destinations/Korcula-Croatia.jpg
Montenegro http://www.chrystal-clear.com/wp-content/uploads/2012/09/Montenegro-Kotor-2.jpg
Serbia http://no-limit.info/travel/services/wp-content/uploads/2014/11/Zaovine_Lake_Serbia.jpg
Macedonia https://ilononthemove.files.wordpress.com/2014/09/170420141184.jpg
Albania http://static.panoramio.com/photos/original/100607957.jpg
Turkey http://www.youngambassadorssociety.org/wp-content/uploads/2014/12/Istanbul-HD-Wallpaper.jpg
Ukraine http://eeua.ru/files/images/kolontitul-2_0.jpg
Belarus (EDITED) https://02varvara.files.wordpress.com/2013/11/00-memorial-church-of-all-saints-minsk-02-16-07-13.jpg?w=1200&h=850
Russia https://justtalkintrash.files.wordpress.com/2014/03/image2.jpg

These are actually some of my favorite places, but you might want to do a little planning if you wish to visit them.

Not to put too fine a point in it, but the limit is 90 days, not 13 weeks (91).

James, Why have you put a link to a picture of Warsaw against Belarus?

Croatia is due to join the Schengen Area some time in 2016.
Bulgaria and Romania have been due to join Schengen for the past few years, the date keeps getting put back. They may be in Schengen by August next year.

"have a common system of visas named Schengen" - not true. The object of the Schengen treaty (named after the town it was signed in) is to make it easier for EU citizens to travel around without having to show there passports or ID at every border. A side effect is that this means they have to have a common set of rules about allowing non EU/Schengen citizens in, whether they need a visa etc.

Chris F., where would you rather be? Minsk or Warsaw?????????? Okay, I cut and pasted too fast. Its fixed. Thanks for the heads up.

And this might help with Schengen visas http://www.schengenvisainfo.com/

James, Warsaw any day.
I don't think Belarus is on many people's "must see" lists. And virtually everybody needs a visa to get in, even EU citizens such as poles.

For historical reasons Warsaw to be sure, well worth a return trip.