Wir ziehen nächste Woche in eine neue Wohnung und habn schon alles per Handschlag mit dem Vermieter geregelt. Alle Umzugsvorbereitungen laufen bereits. Nun verlangt er plötzlich eine höhere Kaution. Darf mein Vermieter die ursprünglich vereinbarte Kaution einfach erhöhen?

Wieviel verlangt er denn? Zulässig sind maximal 3 Kaltmieten
Nein, auch mündliche Verträge sind einzuhalten. Nur muss es oder du es beweisen können.

Frag am besten den Mieterverein. Aber wenn Dir die Kaution zu hoch ist, mußt Du nicht unterschreiben. Dann muss er sich einen anderen Mieter suchen und vielleicht künftig überlegen was er sagt und dann auch wirklich tut

Zulässig sind max. 3 Kaltmieten, mehr darf er nicht verlangen. Wieviel verlangt er denn? Der Vermieter muß dier aber eine Ratenzahlung von 3 Monaten gewäher, d.h. das Geld ist demnach ja eh nicht weg. Zu Deiner Siccherheit lege aber wenn du die Kaution bezahlst ein Kautionssparbuch an, da kann weder dein Vermieter noch du alleine an dieses Geld, sondern dieses geht nur wenn ihr beide zur Bank geht.

Wenn Du das mündlich vereinbarte nicht beweisen kannst - ja. Aber nur bis auf max 3 Monatskaltmieten. Auch Du könntest vom Vertrag zurücktreten, weil es ja keinen gibt. Aber wahrscheinlich ist das nicht in Deinem Interesse, mangels Alternative.
Ich finde es wirklich erstaunlich, dass Du so eine wichtige Sache nicht schriftlich festhältst. Er könnte ja auch einfach die Miete im späteren Vertrag höher ansetzen, denn Du wirst dann ja nicht mal eben so wieder ausziehen. Ein Umzug ist ja nun auch nicht gerade billig.