I am currently doing a paid internship in South Korea and have a 3 Months C4 visa (something went wrong during the 6 months visa preparation). As my internship lasts for 6 Months I have to leave Korea, apply for another C4 visa and come back. Is it possible to apply for such a visa at the Korean embassy in Japan with just a tourist status? (without having a resident status in Japan)
In theory, yes, it's possible. In practice, not necessarily:
While any Korean Embassy or Consulate General overseas should issue a visa to any applicant that meet the application criteria, that is, unfortunately, not always the case - the applicant is always at the mercy of the official dealing with their application & some Embassies or Consulate Generals will only issue visas to residents, not applicants they term 'passing though' the region. Plus, there are a growing number of overseas Embassies or Consulate Generals that will not issue C4 visas at all.
And Fukuoka, the most popular destination for Korean visa runs thanks to the ferry links to Busan, is on their (strictly unofficial, mind you) "does not issue" list.
While the official guidelines for C4 issuance do not require proof of Japanese residence, the Oct 2014 guidance (click the PDF link) for applying for visas at Korean embassies/consulates in Japan imply that only Japanese residents can apply:
In general, you must submit your visa application to a jurisdictional diplomatic mission only.
So I would definitely call ahead and confirm with the particular embassy/consulate you were planning to apply at, before you go ahead and book flights etc.