Document submitted to Hitler by Himmler: I believe that this is Himmler memorandum of 25 May 1940. In this memorandum on Jewish policy, Himmler suggested to Hitler "seeing the concept 'Jew' . . . completely extinguished by the possibility of a huge emigration of all the Jews to Africa or one of the colonies." This was in May 1940, when plans like the Madagascar resettlement plan were being considered as a way to remove all Jews from Germany's sphere of control. Himmler famously also noted in this memo his not wanting to use "the Bolshevist method of the physical extermination of a people" because this method in his view was "un-Germanic and impossible." Hitler called the memo "good and correct," and in its wake both the Foreign Ministry (Franz Rademacher) and Heydrich in the RHSA were working on schemes to remove Jews from Europe to Madagascar. This is covered well in Longerich's book Holocaust; the time period was about a year before the German invasion of the Soviet Union and the start of large-scale murder operations against the Jewish population there and over a year and a half before the first death camps went into operation. Longerich concludes that, impractical as the expulsion of Jews to an SS-colony in Madagascar was, it "is precisely the lack of feasibility in this plan that points up the cynical, calculating nature of German Judenpolitik: the idea that millions of European Jews would be deported to Madagascar for years and years--without even considering the 'punishment measures' that Rademacher envisaged--a large proportion of the transported Jews would presumably die there relatively quickly as victims of the hostile living conditions they would meet, all this makes it perfectly clear that behind this project lay the intention of bringing about the physical annihilation of the Jews under German rule." This plan was a replacement for an earlier, failed plan to resettle Jews into a "reservation" in Poland. Longerich: "For a period of a few months, then, 'Madagascar' stood for 'anywhere' that might permit the execution of a 'final solution,' or in other words for the option of initiating a slow and painful end for the Jews of Europe in conditions inimical to life."
Verbal formulation of policy: Yes, and also communicated verbally. I will find references for this later, as I am not near my secondary sources at the moment.
Copy of the memorandum: I believe that the document is in English translation in J. Noakes & G. Pridham, Nazism 1919-1845, Vol. 3 (1988). I haven't read it and don't own this book.