It couldn't have worked, for numerous reasons.
First of all, in most cases you can't just publicly go around shooting people, including children, without raising the ire of the general population (even the antisemitic one) and still keep up the image the Nazis wanted to have at home and in most occupied countries of the Western/Central Europe, which wasn't "criminal bloody monsters sowing chaos and death". This seems like an obvious point, leaving aside their eventual failure on that score. With such behavior the whole Allied propaganda efforts would have been unnecessary since the Nazis would have been doing the job for the Allies. (Add to this that they even liked to think of themselves as "humane" and not barbaric; one of the (secondary) reasons for the gassings was that it was allegedly a more humane method.) So this one reason was already sufficient against the "shoot on sight" approach.
It follows that the program would have to be secret. But the Nazis received quite a backlash from the pseudoeuthanasia program, even though it was officially secret (and nevertheless people knew). They even stopped the centralized T4 program (though the killings continued, less systematically among the civilian population, more systematically among the camp population) . Because you can't hide stuff like this locally. So the victims had to be transported to far away regions populated by the peoples about whose opinion the Nazis cared the least. That would be the occupied Polish and Soviet territories.
In the USSR and Poland the executions were more open (and sometimes the locals participated), but even there for large-scale actions certain camouflage measure were usually taken, like at Babiy Yar, where the shootings were done under the pretense of allegedly deporting the Jews somewhere and the locals couldn't see the shootings themselves. (Though of course the Nazis did not try really hard, so the locals knew anyway. It was hard not to.) And even in the camps on these territories camouflage measures were still taken.
The second point is simple: body disposal. Decentralized, individual shootings are a mess. Especially in a city, where you usually can't bury the body easily. Not to mention all the problems that arise afterwards (think two steps ahead) or the absolute lack of secrecy (the first point applies here too).
The third point is logistical: finding the victims. If you go from home to home just killing everyone, you need enormous manpower to do it quickly, or you will fail, since your victims will flee. It becomes a mess. It just doesn't work logistically. You have to make victims sort of come to you. Under the pretense of "merely" deporting them. "Legally".
The fourth point: labor force. The Jews able to work were mostly to be exploited for work. Especially those sent to Auschwitz. That was the plan, see the Wannsee protocol. So, once again, the "shoot on sight" policy breaks down immediately (with some exceptions, like the Soviet Jewish males, many of whom were shot immediately in the first months of the invasion of the USSR since the Soviet Jews were seen as especially pernicious by the Nazis).
The fifth point: shootings are inherently less efficient than mass gassings. First of all, there are harmful effects on the executioners. Von dem Bach-Zelewsky in one of his postwar statements described at length how Himmler witnessed an execution of Jews by shooting and was convinced that it had a negative effect on the shooters. A better method had to be found, and gas was experimented with for the mass murder and found acceptable. You can read the excerpt here (scroll down to the images of the 4 pages).
Furthermore, if you gas e.g. 2000 people in a stationary gas chamber, you only need the guards to push them in, and one or two people to introduce the gas (in Auschwitz - one or several Zyklon B cans; in the Aktion Reinhardt the exhaust gases of gasoline engines were used; in both cases the costs per victim were laughably cheap). The body disposal was left to the Jewish special teams. If you're using gas vans, you can kill maybe 50-80 people at a time pro van, so here the efficiency plays a secondary role, but the stress on the executioners is significantly lower.
On the other hand, if you're shooting 2000 people, you need at least as many bullets, and a considerable shooting team (that will be traumatized to boot), as well as lots and lots of time. I think at this point it should be quite obvious that mass gassing in stationary gas chambers is by far the most efficient industrial mass murder method. (Though in "the East" the shootings still could be more expedient from case to case.)
The sixth and final point is that centralized murder in special extermination camps also meant centralized utilization of the stolen property, and even of the body parts (such as golden teeth and even hair). It's a more orderly way to conduct such robbery, and when we're talking about the occupied or Nazi-allied countries which were officially not part of the "Reich", it was also an excuse to funnel the deportee belongings (incl. currency, jewels, precious metals and whatever else the deportees were taking with them), which otherwise would have to stay in the countries of origin, to the "Reich".
The combination of these points (and probably some which I didn't mention) shows that the Nazis' solution was the most efficient one.
Hi! As this question pertains to basic, underlying facts of the Holocaust, I hope you can appreciate that it can be a fraught subject to deal with. While we want people to get the answers they are looking for, we also remain very conscious that threads of this nature can attract the very wrong kind of response. As such, this message is not intended to provide you with all of the answers, but simply to address some of the basic facts, as well as Holocaust Denial, and provide a short list of introductory reading. There is always more than can be said, but we hope this is a good starting point for you.
##What Was the Holocaust?
The Holocaust refers the genocidal deaths of 5-6 million European Jews carried out systematically by Nazi Germany as part of targeted policies of persecution and extermination during World War II. Some historians will also include the deaths of the Roma, Communists, Mentally Disabled, and other groups targeted by Nazi policies, which brings the total number of deaths to 11-17 million. Debates about whether or not the Holocaust includes these deaths or not is a matter of definitions, but in no way a reflection on dispute that they occurred.
##But This Guy Says Otherwise!
Unfortunately, there is a small, but at times vocal, minority of persons who fall into the category of Holocaust Denial, attempting to minimize the deaths by orders of magnitude, impugn well proven facts, or even claim that the Holocaust is entirely a fabrication and never happened. Although they often self-style themselves as "Revisionists", they are not correctly described by the title. While revisionism is not inherently a dirty word, actual revision, to quote Michael Shermer, "entails refinement of detailed knowledge about events, rarely complete denial of the events themselves, and certainly not denial of the cumulation of events known as the Holocaust."
It is absolutely true that were you to read a book written in 1950 or so, you would find information which any decent scholar today might reject, and that is the result of good revisionism. But these changes, which even can be quite large, such as the reassessment of deaths at Auschwitz from ~4 million to ~1 million, are done within the bounds of respected, academic study, and reflect decades of work that builds upon the work of previous scholars, and certainly does not willfully disregard documented evidence and recollections. There are still plenty of questions within Holocaust Studies that are debated by scholars, and there may still be more out there for us to discover, and revise, but when it comes to the basic facts, there is simply no valid argument against them.
##So What Are the Basics?
Beginning with their rise to power in the 1930s, the Nazi Party, headed by Adolf Hitler, implemented a series of anti-Jewish policies within Germany, marginalizing Jews within society more and more, stripping them of their wealth, livelihoods, and their dignity. With the invasion of Poland in 1939, the number of Jews under Nazi control reached into the millions, and this number would again increase with the invasion of the Soviet Union in 1941. Shortly after the invasion of Poland, the Germans started to confine the Jewish population into squalid ghettos. After several plans on how to rid Europe of the Jews that all proved unfeasible, by the time of the invasion of the Soviet Union in 1941, ideological (Antisemitism) and pragmatic (Resources) considerations lead to mass-killings becoming the only viable option in the minds of the Nazi leadership. First only practiced in the USSR, it was influential groups such as the SS and the administration of the General Government that pushed to expand the killing operations to all of Europe and sometime at the end of 1941 met with Hitler’s approval.
The early killings were carried out foremost by the Einsatzgruppen, paramilitary groups organized under the aegis of the SS and tasked with carrying out the mass killings of Jews, Communists, and other 'undesirable elements' in the wake of the German military's advance. In what is often termed the 'Holocaust by Bullet', the Einsatzgruppen, with the assistance of the Wehrmacht, the SD, the Security Police, as well as local collaborators, would kill roughly two million persons, over half of them Jews. Most killings were carried out with mass shootings, but other methods such as gas vans - intended to spare the killers the trauma of shooting so many persons day after day - were utilized too.
By early 1942, the "Final Solution" to the so-called "Jewish Question" was essentially finalized at the Wannsee Conference under the direction of Reinhard Heydrich, where the plan to eliminate the Jewish population of Europe using a series of extermination camps set up in occupied Poland was presented and met with approval.
Construction of extermination camps had already begun the previous fall, and mass extermination, mostly as part of 'Operation Reinhard', had began operation by spring of 1942. Roughly 2 million persons, nearly all Jewish men, women, and children, were immediately gassed upon arrival at Bełżec, Sobibór, and Treblinka over the next two years, when these "Reinhard" camps were closed and razed. More victims would meet their fate in additional extermination camps such as Chełmno, but most infamously at Auschwitz-Birkenau, where slightly over 1 million persons, mostly Jews, died. Under the plan set forth at Wannsee, exterminations were hardly limited to the Jews of Poland, but rather Jews from all over Europe were rounded up and sent east by rail like cattle to the slaughter. Although the victims of the Reinhard Camps were originally buried, they would later be exhumed and cremated, and cremation of the victims was normal procedure at later camps such as Auschwitz.
##The Camps
There were two main types of camps run by Nazi Germany, which is sometimes a source of confusion. Concentration Camps were well known means of extrajudicial control implemented by the Nazis shortly after taking power, beginning with the construction of Dachau in 1933. Political opponents of all type, not just Jews, could find themselves imprisoned in these camps during the pre-war years, and while conditions were often brutal and squalid, and numerous deaths did occur from mistreatment, they were not usually a death sentence and the population fluctuated greatly. Although Concentration Camps were later made part of the 'Final Solution', their purpose was not as immediate extermination centers. Some were 'way stations', and others were work camps, where Germany intended to eke out every last bit of productivity from them through what was known as "extermination through labor". Jews and other undesirable elements, if deemed healthy enough to work, could find themselves spared for a time and "allowed" to toil away like slaves until their usefulness was at an end.
Although some Concentration Camps, such as Mauthausen, did include small gas chambers, mass gassing was not the primary purpose of the camp. Many camps, becoming extremely overcrowded, nevertheless resulted in the deaths of tens of thousands of inhabitants due to the outbreak of diseases such as typhus, or starvation, all of which the camp administrations did little to prevent. Bergen-Belsen, which was not a work camp but rather served as something of a way station for prisoners of the camp systems being moved about, is perhaps one of the most infamous of camps on this count, saw some 50,000 deaths caused by the conditions. Often located in the Reich, camps liberated by the Western forces were exclusively Concentration Camps, and many survivor testimonies come from these camps.
The Concentration Camps are contrasted with the Extermination Camps, which were purpose built for mass killing, with large gas chambers and later on, crematoria, but little or no facilities for inmates. Often they were disguised with false facades to lull the new arrivals into a false sense of security, even though rumors were of course rife for the fate that awaited the deportees. Almost all arrivals were killed upon arrival at these camps, and in many cases the number of survivors numbered in the single digits, such as at Bełżec, where only seven Jews, forced to assist in operation of the camp, were alive after the war.
Several camps, however, were 'Hybrids' of both types, the most famous being Auschwitz, which was a vast complex of subcamps. The infamous 'selection' of prisoners, conducted by SS doctors upon arrival, meant life or death, with those deemed unsuited for labor immediately gassed and the more healthy and robust given at least temporary reprieve. The death count at Auschwitz numbered around 1 million, but it is also the source of many survivor testimonies.
##How Do We Know?
Running through the evidence piece by piece would take more space than we have here, but suffice to say, there is a lot of evidence, and not just the (mountains of) survivor testimony. We have testimonies and writings from many who participated, as well German documentation of the programs. This site catalogs some of the evidence we have for mass extermination as it relates to Auschwitz. I'll end this with a short list of excellent works that should help to introduce you to various aspects of Holocaust study.
##Further Reading
/u/estherke has previously answered Why did the Nazis spend time and resources transporting Jews to concentration camps by train to gas them rather than shooting them on the spot?
/u/coinsinmyrocket has previously answered Some Holocaust survivors were moved from camp to camp. Why did the Nazis spend all that time moving them around? Why not simply kill them?
/u/commiespaceinvader explains in a multipart answer about the Evolution of the Holocaust.