It would be a matter of going through the newspaper archives of the time, these are not all online, unlike more contemporary archives.

However, Isabel Virginia Hull, in the book Absolute Destruction: Military Culture and the Practises of War in Imperial Germany writes:

Negotiations were a sore point with public opinion, too ... the Tägliche Rundschau expressed the widespread indignation at such an idea: "Humanity belongs in the right place—for the moment, however, the national honor and the future of the colony require punishment and suppression of the rebels via force of weapons and the superiority of the white man, but not via peace negotiations, which would recognize the mutineers as legitimate combatants."

Public opinion, the Kaiser, and General Staff were of one mind in demanding a clear victory of weapons.

and

The demand for punishment reflected widespread public opinion in the colony and in Germany. The Berliner Zeitung was typical: “We must make a repeat of this uprising impossible under all circumstances by sharp and ruthless punishment.” So on the whole, public opinion. Much more recently, we have

She also writes:

The greatest scandal of military occupation administration was the annihilation of the Nama in the prison camps

this is foot-noted to Deutsch-Südwestafrikanische Zeitung (14 Dec. 1904) (footnote 85).

So it looks like public opinion began to turn once the war was engaged and the brutality exposed.

More recently, more contemporary reports are categorical on the then German brutality when in 2004, 100 years after the Herero-German War, the German government officially apologised:

for the first time yesterday for a colonial-era genocide which killed 65,000 Herero people in what is now Namibia. "We Germans accept our historic and moral responsibility and the guilt incurred by Germans at that time," said Heidemarie Wieczorek-Zeul, Germany's development aid minister, at a ceremony to mark the 100th anniversary of the Hereros' 1904-1907 uprising against their rulers.

"The atrocities committed at that time would have been termed genocide," she said, according to Associated Press.

"...Everything I have said was an apology from the German government," Mrs Wieczorek-Zeul

Trying to dig up the specific reactions of the general public from that time period would be very difficult, if not impossible. But judging from the attitude of the time period there was probably not an "outrage" as we would define it today. For similar projects I've looked at old newspapers from the time period and looked for editorials. Usually there aren't any because the press was arguably "less free" at the turn of the century. The early 20th century was truly the last days of colonialism (so-called modern colonialism is usually metaphorical language). Public opinion was shifting but it was a gradual change. Many European countries were beginning to relinquish their colonies but there were many voices on both sides of the argument.

So I doubt the public thought much about it, genocides of Africans by Europeans was not uncommon.I don't think he was relieved of command because of this one incident.

Finally there is some interesting evidence from today. This BBC article says that descendants of Von Trotha apologized to the Herero chiefs while government officials still do not apologize officially. I find that rather strange but often governments don't like apologizing retroactively or at all.

"The German government has expressed "regret" at the killings, and a visiting minister apologised in 2004 in general terms, but she avoided specifically saying sorry for the massacres. "

Q: What was the contemporary German public opinion on the Herero Genocide? However, the source cited in wikipedia does not provide any details of the public outrage. I would like to know what form did it take? Did people write editorials? Did deputies protest in the Reichstag? Rallies? Lectures? Petitions? Demonstrations?

It was a very controversial 'event'. So much so that it prompted an entire election, which was popularly named after it: the "Hottentottenwahlen" (= Hottentot elections. 'Hottentotten' being the – even at the time considered – racist epiteth for the Herero and Nama people.) The election itself is indication for a deep divide in public opinion over acts and methods in the colony.

Public debates in parliament and prompting an election

Especially the Socialists/Social Democrats from the SPD were appalled by the dispatches describing the cruelty of the German military. The ensuing election campaign itself then moved a bit away from this and focused again more on domestic issues and general colonial policy, though the original outrage about the genocide still dominated the agendas. Note that 'the outrage' was of course confined to Socialists and other left leaning parties, and the Catholic Center-Party — as of course conservatives perpetrated it and pretty much were in agreement with 'strong leaders dealing out harsh measures to those who deserved it'. A recipe for excellent polarisation of the electorate.

The election was called the Hottentot election because its cause and the election campaign were determined by the Herero war in the colony of German Southwest Africa, but above all by the Nama uprising that was connected with it. The Nama were called "Hottentotts" - a derogatory term even then. The ongoing colonial war, which was associated with high costs, led to a political crisis in Germany, after the German government had requested a supplementary budget of 29 million Marks for the war in Deutsch-Südwestafrika on August 2nd, 1906, in the Reichstag. Especially the Social Democratic Party of Germany (SPD) refused to agree to further funds in view of the reckless warfare with numerous victims among the estimated 20,000 Nama. Initially, the Reich leadership had tried to resolve the conflict by making a certain amount of concessions. Above all, Matthias Erzberger, a member of the Centre, sharply criticised the extensive expenditure and argued against the colonial wars. This led to the fact that the Centre faction, too, partly against its will, rejected the supplementary budget. In contrast, conservatives and national liberals vehemently advocated the continuation of the colonial war. The vote on 13 December resulted in a narrow majority of 177 to 168 against the supplementary budget. […]

On the same day, Imperial Chancellor Bernhard Fürst von Bülow ordered the dissolution of the Reichstag by decree of Wilhelm II, who also supported this step in terms of content. One reason for the dissolution in the face of a not very important issue was that not only the Emperor but also large sections of the bureaucracy had become increasingly reluctant to accept the Centre's strong position. Bülow, who did not share this position and would have liked to continue to rely on the Centre, gave in. He hoped to restore his tarnished position of trust with the emperor by trying to establish a new political government majority. As things stood, the only way to do this was to resume cooperation with the former cartel parties of conservatives and national liberals, extended to include the left-wing liberals. After the death of Eugen Richter the year before, a willingness on the part of the left-wing liberals to support the government had been apparent for some time. This alliance actually came about and is generally referred to as the Bülow Bloc. It was not least through the mediation of the government that electoral agreements were reached between the parties involved for the run-off elections, which have now become commonplace. […]

In the run-up to the elections that are now approaching, it was above all the government itself that set the tone with its propagation of a majority that was reliable in "national issues" and the fight against social democracy, which was fought as an enemy of the monarchy, religion and property, and against the nationally unreliable Centre Party. The aim was to unite the cartel parties and the left-wing liberals into a nationally-minded, anti-socialist and anti-clerical bloc. This was supported by a newly founded '"Reichsverband gegen die Sozialdemokratie'.
_{— WP: Reichstagswahl 1907}

Epilogue: The polarising debates led to a higher voter turn-out over-all. The perverted voting system then ensured that the SPD won half a million more votes than in the last election but lost half of their seats. Yet, the SPD still remained the strongest party in terms of votes received by a majority of 10%.
(SPD: 28.9% – 43 seats, Centre Party: 19.4% – 105 seats; for comparison Antisemite Parties: 3.1% – 21 seats!)

Public debate in newspapers, polarised along party line affiliation

For an example of the contemporary debate: The Social Democrats' newspaper Vorwärts is completely digitised. In the issue 25.09.1906 we can read how they argued. Costly and senseless bloodshed, greedy and unjust land grabbing, followed by cruel extermination policy, ignoring resolutions of parliament, even sympathy for aims, motivations of the colonised. This paper alone discusses the problem in around ~300 articles.

More conservative-nationalist, but still 'center', the Vossische Zeitung is also digitised and took part in the debate. Shortly before the election, on 21. January 1907 they felt the need to publish 'election poetry' sent in by readers. The first 'poem' starts

Seid einig, einig, einig!

Werden wir die schwarzen Brüder diesmal endlich unterkriegen, oder soll in Deutschland wieder Welsche Pfaffheit glorreich siegen?

Seht ihr, wie sie frech sich brüsten, Höhnend euch von ihrem "Turme", Und ihr zaudert euch zu rüsten Alle, Mann für Mann, zum Sturme?

Auf, was deutsch ist, eng im Bunde! Eins nur darf euch heute kümmern: Seid nicht klein zur großen Stunde — Und Zwing-Uri liegt in Trümmern

_{Very roughly: Unity, unity, unity! Will we finally get the Black Brothers in the dust this time? Or shall in Germany again catholic parsonry triumph gloriously? You see how they boldly boast, mocking from their "tower"? And you hesitate to prepare, all of you, man for man, for the storm? On what is German, close together! There's only one thing you can worry about today: Don't be small at the great hour -And Zwing-Uri lies in ruins.}

Meaning: 'Show the blacks their place in the colonies or bad radicals and Catholics will triumph, no time for dissent, it's war, the fatherland, make Germany great again' etc blabla. The incoherence of this style of thinking is as usual built in.

If we'd get to the really right-wing publications, things are of course even uglier to read, so I'll spare you that.

Historical analysis of the debates and their consequences

A more detailed analysis of the working class and SPD agitation and opinion as well as consequences of the election (which some misinterpret as 'colonialist turn' for the SPD) and by contrast its oponents is:
— Jens-Uwe Guettel: "The Myth of the Pro-Colonialist SPD: German Social Democracy and Imperialism before World War I", Central European History, Vol. 45, No. 3, 2012, pp. 452-484.

In stark contrast:

The colonial atrocities remained a topic of the social democrats during the election campaign, albeit only very limited. It speaks for the importance accorded this topic that the topic was never really taken up by the opponents. A reason for this might lie in the fact that the nationalist forces were not really concerned about the actual events in the colonies, but took issue with the fact that political parties and the public at large assumed the right to discuss these. Still, the extremely violent nature of the wars in GSWA [German Southwest Africa] did not really play a role in the public discourse of the metropole at that time. It was never raised as a topic on its own, nor was the violence condoned either. […]

The issue is more complex, however, and can best be explained by explicating the role played by the veteran’s associations, particularly the nature of the consensus reached during the elections. These associations are characterised by their reactionary nature, which puts them into opposition to the fundamentally aggressively chauvinist, radically right-wing groups, such as the Alldeutsche Verband (Pan-German League). Their rather unrefined social-Darwinist discourse and clear war-oriented politics distinguished these clearly from the veteran’s associations.

The extraordinary involvement of the large, otherwise non-political and loyal organisations in these elections indicates that something else was underlying in 1907, namely the quasi-sanctity of the government’s ultimate power of decision. In this they differed fundamentally from the radical oppositional approach of the Pan-Germans. The electorate confirmed the policy hitherto followed and gave carte blanche for the future. As such this [was] endorsing the authoritarian state, the quintessential German Obrigkeitsstaat. Consensus, however, was reached on the question of control of foreign and military policy; no external control should be exerted and therefore the general public would not be involved in decisions taken and procedures to be followed. The public had to remain acquiescent. This opened a space in which anything was possible, regardless.
_{— Matthias Häußler: "“Die Kommandogewalt hat geredet, der Reichstag hat zu schweigen.” How the ‘Hottentottenwahlen’ of 1907 shaped the relationship between parliament and military policy in Imperial Germany", Journal of Namibian Studies, 15 (2014): p7–24.}

A verdict that may be a bit too clean and apologetic. Beside big politics and published opinion, the public discourse also manifested this 'event' in other forms:

Deeply seated in contemporary discourses of progress, modernisation, and the vanishing of whole peoples, popular theatre thus did not have to shy away from depicting the exterminatory character of the colonial war. On the On the contrary, as I have shown, the genocide was a selling factor in Berlin at the time. […]

The example of Circus Busch has shown that popular entertainment sometimes mirrored the univocal, expert discourse of the colonialist bourgeoisie and intersected it with spectacular, mass culture-appropriate stage effects. And in other times, as the example of the Metropol Theater has shown, popular theatre could betray its usual repertoire of politically ambiguous satire by staging clear-cut colonial propaganda. Here, an anxiety about the blurry boundaries of the different colonial epistemes, popular and bourgeois, surfaced in the voices of the critics. What both cases indicate is that the war itself and its genocidal character were not only very present in the German public sphere at the time but in their representation, assuring commercial success for the cultural industry in perpetuating the image of the lives of the Herero as ‘destructible.’
_{— Lisa Skwirblies: "The First German Genocide Enters the Popular Stage: Colonial Theatricality in Berlin, 1904-1908", Popular Entertainment Studies, Vol. 8, Issue 1, pp. 7–20.}

Rohrbach's account and other first hand reports

If the settlement official Rohrbach should be any indication, then his view of these affairs is certainly quite distinct compared to von Trotha, but not simply: "unequivocally deplores the attempt to exterminate the Herero." While it is true that on the mentioned pages he doesn't advocate 'complete extermination'. It is also true that he makes a – in his view – 'more balanced' argument: 'to not kill all the cheap workers', as that would undermine exploitation, profit and manageability. But he also acknowledges

Warfare is, after all, at the mercy of the unfortunate principle of "annihilation" [Vernichtung], and we, who think at first not of warfare in its purest culture, but of the purpose that is to be achieved by war, and of what will come after the war, have nothing to say and may limit ourselves to reading in the local newspapers after 4 or 8 weeks each time what the war leaders or individual war participants telegraph or write home about the situation and the existing intentions.
_{— Paul Rohrbach: "Aus Südwestafrikas schweren Tagen", Wilhem Weicher: Berlin, 1909, p 170. )}

That is, after he wrote on page 8:

Perhaps the first Herero uprising of 1896 dock was punished too mildly. The Negro does not regard leniency of the victor as magnanimity, but as weakness. It is a hard conflict for each of us, who wants to think and act humanely, but who still wants to accept his responsibility.

The sentiment of 'international responsibility' means of course 'sending soldiers to kill'. At least that didn't change much…

Rohrbachs seemingly 'more humane' views of utlitarianist exploitation of natives in that book is by far not the only thing he had to say on the matter in his more than 2500 writings. The Wikipedia characterisation of him is correct in so far as he did write, in no uncertain terms and repeatedly, in another book:

As far as the aspect of humanity was concerned, which was particularly emphasized in Germany in comparison with the order of extermination and which also led to the rectification of General von Trotha by the Imperial Chancellor, it must be admitted in itself that under certain circumstances, in order to protect the peaceful settlement of the whites from a simply culturally incapable, predatory indigenous tribe the actual extermination of which may become necessary.
_{— Paul Rohrbach: "Deutsche Kolonialwirtschaft Südwest-Afrika", Buchverlag der "Hilfe": Berlin-Schöneberg, 1907, p352.}

Quite conveniently, a small collection of Rohrbach's and other colonialists' racist attitudes and opinions is woven into a dissertation that analyses German colonial policy, and its debates over the sought after Dernburg-reforms:
— Sören Utermark: "„Schwarzer Untertan versus schwarzer Bruder“. Bernhard Dernburgs Reformen in den Kolonien Deutsch-Ostafrika, Deutsch-Südwestafrika, Togo und Kamerun", Dissertation, Universität Kassel, 2011. (PDF)

The article in the German Wikipedia (for some perhaps telling reason its title refers to "uprising" vs. "genocide") mentions pressure exerted by protestant missionaries' churches ("Der Druck der Öffentlichkeit, besonderes der evangelischen Missionskirchen, wuchs.")

It quotes a German PhD thesis from 2004 that provides further information (e.g. on page p. 182). It includes a detailed account of the battle of Waterberg and its tragic aftermath in the Omaheke desert. It also confirms Lothar von Trotha's harsh individual stance and imposed methods but also mentions protests from his staff and that some (sadly few) Hereros made it through the Omakehe desert alive.

In terms of public outcry in Germany, it points to activities by the "Rhenish Missionary Society", which led to a reaction by Chancellor Bernhard von Bülow and to von Trotha's recall from colonial service and return to Germany in 1905 (translation courtesy of Google here):

Insbesondere die Rheinische Mission bemühte sich um eine Befriedung des Konfliktes und verhandelte mit dem Auswärtigen Amt und dem Reichskanzler in Berlin. Dabei kritisierte sie in aller Schärfe von Trothas Proklamation. Pastor Hausleiter von der Rheinischen Mission bat Reichskanzler von Bülow in einem Schreiben, Missionare zu den Aufständischen zu entsenden, um diese zur Übergabe zu bewegen. Außerdem sollten sich die Missionen um die Alten, Kranken, Frauen und Kinder kümmern sowie Zufluchtsorte für diejenigen Herero aufbauen, die zwar am Aufstand nicht aber an den Mordtaten gegen Weiße beteiligt waren.

Again, there is a bit more further information in a German-language diploma thesis from 2010. It analyses the Rhenish Missionary Society's publications from the time (and seems to arrive at or start from a more skeptical view as to the alleged importance of the society's noble role as viewed or presented in retrospect from a "white" angle.)

BTW, whether this was "genocide" or not, von Trotha would not have been able to pursue it after 1905 (e.g. up to 1907 as implied in the question), for 1904 was the year of the incidents and 1905 was when he was transferred. The 1911 Encylopaedia Britannica, not always a reliable modern source on colonialism, gives a (to this reader's eyes) relatively fair account of the main actors involvements, but adds some own confusing language ("concentration camps were established in which some thousands of Herero women and children were cared for").

Further evidence could perhaps be recovered from German newspapers at the time (e.g. a Vienna-based newspapers provides a free online archive going back to 1848). However, I currently do not know any such source with a convenient online index. It also seems as if Ludwig von Estorff, one of the officers who tried to stand up to von Trotha in 1904, later had books published about his time in Namibia: They are (sadly) out of print by now.

UPDATE: Paul Rohrbach's book Aus Südwest-Afrikas schweren Tagen (1909) is a collection of diary entries from 1903 to 1905. During that time the author was a senior official in then German South-West Africa. He mentions the Rhenish Missionary Society several times in passing but not in a way that would suggest his own affiliation. There also frequent references to the "Siedlungsgesellschaft". The report reveals a perspective observer and able administrator, even with a sense of humor (translation courtesy of Google):

Herr Schmerenbeck meinte beim Einreiten, als wir alle großen Durst feststellten, daß irgendwo in einem Zimmer noch eine Kiste Bier stehen müsste. Statt der Kiste fanden wir in dem betreffenden Raum aber einen kleinen Termitenbau, und als der mit der Schaufel auseinandergeschlagen wurde, fanden sich auch ca. 20 Flaschen Bier unversehrt darin vor. Die Termiten waren ins Haus gekommen und hatten die Kiste samt den Strohülsen der Flaschen rein aufgefressen. Es ist wirklich wahr: nur Glas und Metall sind vor ihnen sicher. Aber die Flaschenkorken? An die hatten sie wegen der Stanniolhülle nicht herangekonnt.

With respect to pressure from public opinion in Germany it may be relevant that Rohrbach throughout his tenure seemed concerned about a general lack of interest in the colony's fate back in the home country: this would seem to suggest there was no proper basis for raising a broad opposition, e.g. due to lack of information. Rohrbach mentions and severely critizes General von Trotha several times, although he mentions the "genocide" incident only once in passing and regrets a fifty percent mortality rate. While he exhibits many European prejudices opposite Africa that were typical for his time, I find it very hard to believe that he "was an advocate of eradicating native Africans in order to make room for German colonists", as was mentioned. The following excerpt (allegedly from the June 19, 1904 diary entry) may sum up his views as good as any (again, translation courtesy of Google):

Wir alle haben nun die Furcht, daß der Übergang des Oberbefehls an einen General, der nie in Süwestafrika gewesen ist, zusammen mit der fortdauernden notwendigen Vermehrung der neuen Truppen und Offiziere eine Art von Kriegsführung hervorbringen wird, die unseren Bedürfnissen wenig entspricht. Was von den Reden bei der Aussendung der neuen Truppenverstärkungen aus Deutschland verlautet, und was hier über Äußerungen Trothas gleich in den ersten Tagen seines Aufenthalts im Lande kolportiert wird, gibt, fürchte ich, nur Grund zur Sorge. Es ist viel zu viel von der "Vernichtung" der Hereros die Rede. Das hieße auf das Übel des Aufstandes ein zweites setzen, das schlimmer ist [...] Die Hereros führen einen Freiheitskrieg gegen uns, und sie führen ihn in der Art afrikanischer Barbaren. Auch die Cherusker sollen den römischen Sachwaltern nach der Varusschlacht die Zunge ausgeschnitten und den Mund zugenäht haben -- und das waren unsere Vorfahren.

Rohrbach's book is an interesting read and made me think that Karl May may perhaps have had him in mind as a model for his various (from a modern view also more-or-less tainted) fictional heroes.