Muss man einen Kanuschein haben oder ähnliches, um in öffentlichen Gewässern Kanu zu fahren? Weiß da jemand bescheid? Wie ist das mit einem Erste Hilfe Ausweis?

Nein, braucht man nicht. Es wäre sinnvoll, wenn man des Schwimmens mächtig ist.
Wenn Du mit einer Jugendgruppe oder so eine Tour machen möchtest, dann wäre ein Ersthelfer-Schein sicher für die evtl. Versicherung im Schadensfall hilfreich. Ist aber auch da keine Pflicht.
Nein brauch man wirklich nicht! War grade am Samstag in Berlin auf den Kanälen unterwegs. Es gibt allerdings Stellen die man mit Kanus nicht befahren darf! Das gilt zum Beispiel in berlin für das Regierungsviertel und Umgebung.

Brauchst keine Lizenz.
Viele Tipps und Links: http://www.klicktipps.de/kanufahren.php
Vom befahrenen Gewässer sollte man den Kanuführer haben (mindestens den DKV-Führer). Dann kann man sich über eventuelle Gefahren informieren.
Am wichtigsten für Anfänger: Von Wehren weiträumig wegbleiben!
Wenn du nicht gerade eine Gruppe führst, ist ein Schein nicht erforderlich. Ich habe auch mal eine Kanutour gemacht und in einer Situation habe ich mir aber schon einen erfahrenden Guide gewünscht. Bei unserer zweiten Tour haben wie uns dann wirklich penibel über das Gewässer und seine Strömung etc. informiert. Gut vorbereitet, lief es dann auch viel besser.

wie oben schon geschrieben: Brauchst keine Lizenz.
Aber man sollte wissen und verstehen, was um einen herum passiert. Es ist daher sinnvoll, je nach befahrenem Gebiet sich mal das Buch zum "Sportbootführerschein Binnen" bzw. zum "Sportbootführerschein See" zu besorgen.
Besonders die Bedeutung von Schldern und Schallsignalen sollte man kennen! (bei 5 kurzen Tönen hinter einem ist Äktschän angesagt!!)
Sind etwa in der Mitte dieser Seite zu sehen: http://www.klicktipps.de/segeln.php#knowhow
ältere Versionen kann man aber auch in der Bücherei ausleihen.

Du brauchst auf keinen Fall eine Lizenz, aber es gibt andere Dinge, die man beachten muss:
Wenn man in Frankreich fährt, muss man immer eine Schwimmweste anhaben (im Notfall auf jeden Fall eine mitnehmen!).... Außerdem sollte man sich vorher erkundigen, da es Flüsse gibt, die man zu einem bestimmten Zeitpunkt(z.b. Laichzeit) oder bei zu geringem Wasserstand nicht befahren darf.