First of all, what is your father's full name? I assume from your message that he was in the U.S. Navy but was he in the U.S. Navy Armed Guard or the regular Navy?
Having this additional information about your father would be useful in identifying him aboard the ship in question. Nonetheless I have been able to find some information on SS NORTH KING. A Panamanian-flagged cargo ship, she departed New York on December 22, 1944, sailed to Le Havre, France, arriving there and departing from there on unspecified dates, and arrived in New York on March 2, 1945. There is no indication from the record I found that the ship was elsewhere than New York and Le Havre, except that she made a stop in Halifax, Nova Scotia, in late February 1945, on the return trip. On the other hand, the duration of this voyage (ten weeks) strikes me as too long for a simple over-and-back voyage between New York and Le Havre, so it is possible she made a more roundabout voyage such as what your father described. But ordinarily ships headed for Gibraltar and the Mediterranean would have left from Norfolk, not from New York, and a vessel destined for Reykjavik ordinarily would have had no reason to be anywhere close to Gibraltar. That is not to say it did not happen as described, only that it would have been unusual. A more serious problem is that the NORTH KING's crew manifest does not list your father, assuming his last name was Piotrowski. (Ship and crew manifest information comes from the subscription website Ancestry.com, http://www.ancestry.com/.)
Interestingly, however, I also found this: NORTH KING departed New York on December 22, 1943, destination Liverpool, in convoy HX-272. (Note that this is exactly a year prior to the voyage I mention above.) The ship straggled, meaning she could not keep up with the convoy, perhaps due to mechanical problems, and was left behind to fend for herself. (Such a development would likely have left a very strong impression on anyone aboard.) She eventually made her way to the Azores Islands, far south of the normal convoy route to Liverpool, and close to the more southerly route of convoys between Norfolk and Gibraltar. It is possible that a lone ship, once able to sail again from the Azores, would have continued eastward toward Gibraltar either for further repairs or in hopes of intercepting and joining another convoy or both.
Furthermore, I later found NORTH KING in convoy UR-106, departing Loch Ewe, Scotland, on January 19, 1944, arriving Reykjavik on January 24, 1944. Then she is found in convoy RU-107, departing Reykjavik on February 3, 1944, arriving Loch Ewe, Scotland, on February 7, 1944. On this voyage the ship carried 400 U.S. Navy personnel. Subsequently NORTH KING is found in convoy ON-224, departing Liverpool February 14, 1944, destination Boston. My sources do not include ship arrivals in Boston so I cannot say whether your father was aboard on this voyage. (The information I found on her presence in the above convoys comes from ConvoyWeb, http://www.convoyweb.org.uk/hague/index.html.)
In short, therefore, NORTH KING's voyage between December 22, 1943, and March 2, 1944, placed her in New York as a departure point, later she was in the Azores from which it is arguably possible or likely that she continued to Gibraltar, she was then in Scotland, then in Iceland from which she transported Navy personnel, then again in Scotland before finally returning to North America. Although I cannot confirm your father's presence aboard NORTH KING when she returned to North America (presumably to Boston), this voyage fits your father's description much better than the 1944/1945 voyage. So perhaps your father's recollections are off by a year.
As a further suggestion, you may be able to obtain your father's complete military service record, which may detail his assignments and whereabouts during the time(s) in question, by contacting the U.S. National Archives and Records Administration (NARA). Please see this page from the Armed Guard / Merchant Marinewebsite that I manage: http://armed-guard.com/searchmil.html, in particular section II.A.1. - Records of Individuals - U.S. Military. You will have to contact the National Personnel Records Center, a NARA facility in St. Louis, MO. Provide as much identifying information as you have. There may be a charge for research time, photocopying and mailing, but the Records Center staff will provide an estimate on the cost before beginning work. It would be best if the request came from your father, if he is able, rather than from you. Of course you can do the leg work in preparing a request but the request can be signed by your father. Actually, once you have his military record in hand, that should be more useful to you in obtaining VA benefits than the above information about NORTH KING.
Incidentally, NORTH KING had an interesting history of her own. She was built in Germany in 1903 as a cargo ship, originally named LIEBENFELS. In August 1914 she happened to be in Charleston, South Carolina, when World War I began, and she was detained there by U.S. authorities. In February 1917 her German crew scuttled her and she sank in Charleston harbor. She was raised, claimed and repaired by the U.S. Navy. She was commissioned into the Navy as USS HOUSTON in July 1917 and carried cargo to Europe and also between East Coast and West Coast U.S. ports. She was decommissioned by the Navy in 1922 and sold the same year to a private shipping company, renamed NORTH KING, and sailed under the Panamanian flag. In late December 1941 she was chartered by the U.S. War Shipping Administration for the duration of World War II. She was returned to her private owners in 1946 and was eventually scrapped, believed to be in 1957. (See http://en.wikipedia.org/wiki/USS_Houston_%28AK-1%29.)
Ron Carlson, Webmaster
Armed Guard / Merchant Marine website