This is a valid question. The Game of Thrones TV series began in April 2011, at roughly the same point in time that Martin was delivering the manuscript for the fifth novel in the Song of Ice and Fire book series, A Dance with Dragons. Dragons was published in July 2011 and Martin reported that he had started work on the sixth and planned-to-be penultimate novel in the series, The Winds of Winter, using roughly 200 manuscript pages' worth of material as a springboard to write the next book. Like A Dance with Dragons and A Storm of Swords before it, Martin plans for The Winds of Winter to come in at around 1,500 manuscript pages in length. Martin wrote A Storm of Swords (the third novel in the series, published in 2000) in about two years, so it was not impossible to write this amount in a short amount of time. However, A Dance with Dragons took five and a half years to appear, after a five-year wait for the fourth book in the series. With the well-publicised reasons for those delays dealt with (scrapping the original fourth book in the series a year into the writing and starting again from scratch; and a thorny timeline problem called the Meereenese Knot), it was hoped that the new book would take closer to the Storms timespan to complete than the Dragons one.
As of March 2013, The Winds of Winter remains incomplete. New chapters have appeared, read out at conventions and appearing on Martin's website, and he reports progress being made, but no hard info on page count (a hopeful page count of 400 from a Spanish signing appearance a few months ago later turned out to be an erroneous mistranslation) has been given recently. In addition, Martin has reported taking on more projects than he should have done, with both The Lands of Ice and Fire and more recently The World of Ice and Fire (and its related short story, The Princess and the Queen) taking up more time than first intended. The result of this is that we should not be expecting The Winds of Winter to appear in the near future. I've been mooting a late 2015 release date (with the novel being finished in the first half of 2015) as a realistic date, and with Martin's work decks clearing to allow him to work on the novel full-time only this year, this seems to track (and only if no major obstacles on the scale of the Meereenese Knot arise).
In the meantime, HBO have reached their third season, which will carry them roughly two-thirds of the way through the third novel in the series, A Storm of Swords. Season 4 next year (if commissioned, which seems about 99% likely) will almost certainly see them starting to reach material from the fourth and fifth books in the series (which take place concurrently), which means that within not too much time at all they will be breathing down Martin's neck.
The question arises about what will happen next. The first thing they have to do is get through A Feast for Crows and A Dance with Dragons. They will likely take all of Season 5 to do this, along with a chunk from the end of Season 4 and probably a chunk from the start of Season 6. Whilst they're going to be just a book behind Martin fairly imminently, they are also going to take the better part of two seasons' worth of episodes (though extending across three actual seasons) to get through that material. Assuming that they will start reaching Winds of Winter material in late Season 6 and assuming Martin is able to publish The Winds of Winter in late 2015, that will get HBO the book at just about the time they'd need to be filming the next season (they'd actually need it for around June or July of that year, but the MS will be close enough to completion by then that Martin can simply give them information from that).
Of course, if The Winds of Winter is as huge as advertised, it may mean that HBO would take an additional two seasons to get through that material, extending from Season 6 into a potential eighth season. However, at the point another problem rears its head: how long is the HBO series itself going to last?
In the past, showrunners David Benioff and D.B. Weiss have mooted anything from 70 to 90 episodes - seven to nine seasons - to tell their story. This gives them flexibility to end the story after seven seasons if the show's popularity is waning, or continue for nine if the show's popularity remains buoyant. Other issues will play a role in this, such as actors decided to leave or becoming so famous thanks to the show that contractual negotiations become prohibitively expensive (most of the original cast signed six-year deals, which will have to be extended come Season 7). But nine seasons is the longest the show is likely to go on for, and even that seems optimistic when you realise that no HBO drama series, not even the mega-popular The Sopranos, has lasted longer than six.
Even if we assume nine seasons is the lifespan of the show, that clearly leaves problems. Martin has indicated he imagines A Dream of Spring - the mooted seventh and final novel in the series - will also needed to be about 1,500 manuscript pages just to wrap everything up satisfactorily. That means a likely further 3-4 years (at absolute best) to bring the books to completion after The Winds of Winter is finished. This clearly puts the publication of A Dream of Spring and the arrival of the final season of the show at about parity, and again this assumes no major problems occurring. It will also cause problems if A Dream of Spring takes two full seasons or more to tell on screen, since at that point the HBO show is unlikely to still be going. It also means we will see material from the start of A Dream of Spring in Season 8 of the show before the book is published (which will probably be okay with most people, as long as the novel itself comes out before the ninth and final season airs).
This leaves us with a situation that would look like this:
2013: Season 3 - A Storm of Swords Part 1
2014: Season 4 - A Storm of Swords Part 2/A Feast for Crows/A Dance with Dragons Part 1
2015: Season 5 - A Feast for Crows/A Dance with Dragons Part 2
Late 2015: Possible Winds of Winter release date.
2016: Season 6 - A Feast for Crows/A Dance with Dragons Part 3/The Winds of Winter Part 1
2017: Season 7 - The Winds of Winter Part 2
2018: Season 8 - The Winds of Winter Part 3/A Dream of Spring Part 1
2019: Season 9 - A Dream of Spring Part 2/longest realistic lifespan of the TV series
As you can see, this means that Martin would be required to publish A Dream of Spring by spring 2019 at the latest, and to give the showrunners material from it in the summer of 2018.
The Internet the day after HBO announces that TV show is finishing first or is being axed prematurely.
I would submit that, whilst very tight, this is possible. But there are a host of problems that can arise with this. The outcomes I can see are:
1. GRRM finishes the books before the TV series ends.
This is the scenario laid about above, and seems possible, though tricky. It requires The Winds of Winter to come out in late 2015 at the latest and A Dream of Spring in spring 2019 at the latest, or three and a half years later. I think this last feat will be the most difficult to accomplish, though certainly not impossible. In fact, this possibility is already fairly pessimistic and we may well see Winter (and hence Spring) earlier than the dates I have suggested here, which makes life a lot easier for everyone.
2. The book series extends to eight volumes; HBO finishes first.
With material from Dragons delayed until Winter, it becomes possible this will have a domino effect and material from Winter will likewise be knocked back to Spring. This may cause Spring to be overlong as well, and material will need to be moved back into an eighth volume. In that scenario, HBO will finish first.
3. The TV series has to conclude before nine seasons; HBO finishes first.
This is also entirely possible, in which case we will get a (likely truncated) version of the ending on screen potentially several years before we see the ending in print.
4. The TV series deviates totally from the books and it doesn't matter.
This does not appear to be a major problem, as even with the second season (which deviated more from the books than the first season) they've still stuck with the general timeline of the books, just sometimes taking a different route to get there. The recently-revealed episode titles from Season 3 also suggest they'll be sticking pretty close to the storyline from the books, just perhaps not featuring every subplot and minor character. Still, a situation where the show spins off in a totally different direction and makes up its own ending is also a possibility, if a faint one.
There is of course another question that arises:
Does it matter if HBO finishes before Martin?
If HBO does overtake GRRM, then clearly they are going still be asking his advice, getting him to write (at least) one TV episode per season and following outlines and information he has given them for the later books. The ending we will get on screen will be, at least in some form, similar to the ending Martin envisages for the books. I can also see the showrunners asking Martin to write the last episode of the series (they may do this regardless of if the books are out or not). Some readers, particularly those most frustrated with the long gaps between novels, may even prefer the idea that they will get to find out how the story ends on screen within the next six years or so, rather than waiting potentially longer than that if the series extends to eight volumes, or if the sixth and seventh books take a lot longer than it is hoped to appear.
Obviously the TV series is not covering all of the subplots and character arcs that the novels are, so the books will still be worth reading to find out how those issues are resolved. Of course, purists who want to read the books first and see the TV show later will be left with the quandary of putting the show on hold and somehow avoiding lots of spoilers for years on end until the books come out, which I imagine will be quite difficult to achieve.
Not even this guy can tell us how it's going to go down yet.
What is not going to happen.
The TV show is not going to go on hold for years.
Some people have suggested that the TV show could take 2-3 years off and wait for Martin to deliver the final novels, sometimes citing the fact that other HBO shows have gone more than one year between seasons of a particular show. Whilst that is true, it was only true for shows where it was possible to regroup the whole cast: most of The Wire's cast was made up of local Baltimore actors, who were relatively easy to regroup for the final two seasons, whilst even then they had scheduling issues (resulting in Dominic West's character of McNulty barely appearing in the fourth season). With The Sopranos, being HBO's jewel in the crown, it was possible to simply amass the financial firepower to make it happen. With Deadwood, the cast splitting to many different other shows and projects meant it was impossible to regroup them for the planned TV movies meant to resolve the storyline, and it was too expensive to put them on retainer for several years. Rome has also had a theatrical movie script completed for some years, but cast availability issues - amongst others - have prevented it from happening (I imagine the biggest problem there being Kevin McKidd being cast on Gray's Anatomy as a regular, not mention Ray Stevenson's burgeoning movie career).
With Thrones, almost the entire cast is made up of English and Irish actors who are very commonly seen on TV, in film and on stage over here. Thrones going on hiatus for two or three years would see them splitting to the winds to other projects, and getting them all back together later on would be improbable. Given the size of the cast, it would again be too expensive to put them all on retainer for years on end so they could hang around waiting for the show to come back. Thrones has a slight advantage in that many actors are only needed for 2-3 weeks of filming per season (Charles Dance filmed all of Twyin's scenes for Season 2 in just a fortnight, apparently), but the regulars would also be affected, especially given how much in demand they are likely to be as a result of Thrones's success. There is also the issue of the younger actors growing up in the meantime, which would force unpopular recastings to take place.
Game of Thrones is a juggernaut at the moment, going into production every June like clockwork for airing the following April. Even if the show moves timeslot (a shift to True Blood's summer timeslot has been suggested by fans when that show ends, which may happen after its sixth or seventh season) that would only help out by a few months. The show is not going to stop, pause or go on hold until GRRM finishes the books. It is also not going to last for a dozen or more seasons.
On that basis, Martin has a finite timeframe in which to finish Books 6 and 7 before the show overtakes him. At the moment, it is fully possible for him to achieve this, but the window to do so is closing. If he does not manage it, the question fans of the books and TV series will have to ask themselves is, does it matter? I'll certainly be watching to the end, regardless of if the books come out first (though certainly my preference is for the books to appear first).
As usual, we will have to wait and see. And if there's something that Song of Ice and Fire fans have become very good at, it's waiting.