georgechalhoub, in his answer, has discussed one particular perspective on this issue. I will provide a quick summary of it below (for the sake of collecting information into one answer - for more detail and links, see his answer), and then provide some additional perspectives that demonstrate why this is not a straightforward question. Then, I will give an overall "conclusion". As this conclusion will not be definitive, I am not going to place it at the start of the answer.
From georgechalhoub's answer - Freedom House is a US NGO that focuses on advocacy of freedom and democracy. They have a yearly rating of the levels of political rights and civil liberties in each country. When it comes to the Middle East and related countries, they currently consider Israel, Libya, Turkey, and Tunisia to be the only democracies (the latter three not always being considered part of the Middle East). In addition, they currently consider only Israel and Tunisia to be free, with Kuwait, Lebanon, Morocco, and Turkey being considered "partly free".
As such, if we use Freedom House as a trustworthy source, we would call Israel the only country that is consistently considered Free, Democratic, and Middle Eastern, with Tunisia now being considered Free and Democratic, but usually considered African.
There have been some concerns raised regarding Freedom House, specifically regarding how they rate. Namely, some have asserted, using statistical analysis, that Freedom House has a bias in favour of capitalist and christian nations. This does not make the claim true, but it is a good demonstration of why a single source is not sufficient on a politically charged claim such as this. Other concerns will undoubtedly have been raised regarding the other sources I present - I will not be listing concerns for each one, as I do not consider any one source to be especially reliable.
There are other sources, and conclusions vary depending on which source you consider more trustworthy.
The Economist has what it calls the Economist Intelligence Unit (EIU). They are, in many ways, similar to Freedom House. However, they are based in the UK, are a magazine rather than an advocacy group, and they separate their analysis in a different way.
According to their rankings (here provided via a third party), Israel is the most free and democratic of the Middle Eastern countries... however, Israel is considered a "flawed democracy" rather than a "full democracy". Deeper investigation reveals the reason for this. In most of the aspects that EIU take into account in their rating, Israel performs well, being comparable to many European nations. However, on the measure of "Civil Liberties", Israel performs quite poorly, scoring less than 6 where Australia rates a 10 and Austria rates a 9.
It would seem reasonable to suggest that "Civil Liberties" is a reasonable definition of "freedom", and thus, according to EIU, Israel would not be considered "free" in the way that many of us would define the idea.
If we consider the Economist Intelligence Unit to be trustworthy, then our conclusion would be that Israel is the most democratic and perhaps the most free, but that one couldn't really call it "free and democratic".
The Heritage Foundation (HF) is best described as a "conservative US think tank". As such, their definitions of "free" and "democratic" are somewhat different from those of the above sources. On the issue of "Freedom", they consider economic freedom to be most important.
According to their rankings, HF considers Bahrain to be the most "free" of the Middle Eastern nations, followed by UAE, Qatar, and then Israel. All four are in the "Mostly Free" region ("Free" contains just five nations - Hong Kong, Singapore, New Zealand, Australia, and Switzerland), and all are below United States and United Kingdom.
Of the three that rank higher than Israel, Bahrain is officially considered a Constitutional Monarchy (although some dispute it, saying it's an absolute monarchy), UAE is a federation of monarchies, and Qatar is an Absolute Monarchy with a parliamentary system (in other words, the parliament is a consultative body, with final power lying in the hands of the monarch).
If we take Bahrain to be similar to the UK (which is also a constitutional monarchy), then we could assert that they have similar levels of democracy. If we do this, then one could potentially assert, using these definitions of democracy and freedom, that Bahrain is the most "free and democratic" of the Middle Eastern nations.
Alternatively, we may take the alternative view that Bahrain is actually an absolute monarchy, and if we take Israel as a full democracy, then it is the most "free and democratic". However, Israel is also somewhat questionable, as demonstrated by, for instance, this Israeli Op-Ed, which claims that one can't really consider Israel a democracy, despite its electoral system, much as is claimed of Bahrain.
As such, based on the Heritage Foundation's rankings, and considerations of democracy along a similar vein, we would likely conclude that Israel and Bahrain are comparable regarding "freedom and democracy", with other Middle Eastern nations falling short either on freedom or on democracy.
Another source that considers Economic Freedom is the Fraser Institute (FI). In their report (available here) from 2013, they rank UAE, Bahrain, Jordan, Qatar, Lebanon, and Oman as having greater freedom than Israel. I have already discussed UAE, Bahrain, and Qatar in connection with HF.
Jordan is another Constitutional Monarchy, and according to the Arab Reform Initiative, in their Arab Democracy Index, which does not include Israel, Jordan comes in second place - that is, second most democratic of the Arab nations (first place went to Morocco, which if we consider Tunisia to be "African", then so is Morocco). Without the ability to compare with Israel, we can't say anything definitively, but if any nation would be considered to be in competition for "most free and democratic" by FI, it would be Jordan.
Lebanon is a complicated case - their system is parliamentary confessionalist, meaning that they have restrictions on representation to ensure that various religions get appropriate representation. As such, it is debatable whether this is less democratic, more democratic, more or less fair, etc. Oman is an absolute monarchy.
Based on the Fraser Institute's Economic Freedom measure, we would likely consider either Jordan, Bahrain, Lebanon, or Israel to be the most "free and democratic", depending on how much weighting we give to various factors.
Also published by the Fraser Institute is a Human Freedom Index. According to this, the more general Freedom ranking (which includes both Personal and Economic freedoms) rates highest, among the Middle Eastern nations, Bahrain, Oman, Jordan, Turkey, Kuwait, UAE, Egypt, then Israel. In particular, Israel gets a 4.4 on Personal Freedoms (Egypt gets 5.0, and Bahrain gets 6.6, while Australia gets 8.8 and the US gets 8.7). And Israel gets a 6.86 on Economic Freedoms (Egypt gets 6.82, Bahrain gets 7.23, while Australia gets 7.83 and the US gets 7.93).
On this measure, according to the Fraser Institute, it appears clear that Israel is not at all considered the most "free", either in terms of personal freedom or economic freedom.
From all of this, what can we conclude? Well, Israel certainly is no slouch in the category, but classification as "the only free and democratic country" is very debatable. I've identified four different sources that have different measures of "freedom", and on the basis of these four sources, we would certainly consider Israel to rate well on both measures.
However, the variations in exactly how they're rated demonstrates why this question is not a simple one - whereas most would comfortably define the US as more democratic than North Korea, such clear-cut distinctions aren't always possible. Israel has a democracy. So does Bahrain, Jordan, Lebanon, and Egypt. None of them could be called completely, undoubtedly free and full democracy... but then, the same could be said of the US, the UK, or Australia.
What can be said is that the claim that Israel is the only "free and democratic nation in the entire Middle East", as said by McCain, is simplistic and reductionist, and highly politically charged. A full and detailed discussion of the topic is not feasible in this format.
Screenshot from Wikipedia's page 
