I assumed that it would be something like “(ich erzähle) eine Geschichte über das mal, in dem ich...“ but that doesn’t seem right.
And the more I look up how to translate this idea, the more it seems that German doesn’t really even use a translation of the expression „the time that I...“
Would there be a way to say this sentence : „have I told you about the time that I ...(insert story here)“ ? What would be the closest translation?
The most idiomatic way I can think of is
Hab' ich dir mal erzählt, wie ich eine Gitarre umsonst bekam?
which literally translates to
Did I ever tell you, how I got a guitar for free?
If you want to include a time period, you can say
Hab' ich dir mal von der Zeit erzählt, in der ich als Postbote gearbeitet habe?
Or
Hab' ich dir mal von meiner Zeit als Postbote erzählt?
There is an example of this from literature.
The novel Sult (Hunger) by the Norwegian Knut Hamsun starts with the sentence:
Det var i den Tid, jeg gik omkring og sulted i Kristiania, denne forunderlige By, som ingen forlader, før han har faaet Mærker av den ...
which in English translates to:
It was in that time when I walked around hungry in Kristiania, that strange city no one can leave without being marked by it ...
and in German:
Es war in jener Zeit, als ich in Kristiania umherirrte und hungerte, in dieser seltsamen Stadt, die keiner verlässt, ehe er von ihr gezeichnet worden ist ...
In contemporary German, one would probably rather say
Es war in der Zeit, als ich...
Your question would accordingly translate to:
Habe ich dir [schon] von der Zeit erzählt, als ich ...
However, if it's a about a single event, like:
Did I tell you about the time that I lost my wallet in Vienna?
the translation would rather be along the lines of:
Habe ich dir schon davon erzählt, wie ich meine Geldbörse in Wien verloren habe?
You can use einmal or mal in the dependent clause to express this:
[Kennst du schon] die Geschichte, wie ich mal [von der Polizei verhaftet wurde]?
[Sie erzählte] die Geschichte, wie sie einmal [von der Polizei verhaftet wurde].
Alternatively, there's also a colloquial idiom that's more alike to the English way to put it:
[Kennst du schon] die Geschichte über das eine Mal, als ich [von der Polizei verhaftet wurde]?
"Das eine Mal" is a substantivation of "einmal" here. That idiom is not standard German though, I wouldn't use this in writing. It can also be misunderstood to mean that you want to stress that it happened only once, while in fact you're only saying that it once happened.
If you mean to say that the story happened during a certain period of time ("A story about the time when I worked on a farm in Italy.") that would be a different thing.
... eine Geschichte über die Zeit, als ich auf einem Bauernhof in Italien gearbeitet habe.
Your sentence
Have I told you about the time that I ...(insert story here)?
would be
Habe ich dir schon erzählt, wie ich mal ... (insert story here)?
If you want something with more flourish, like in old stories, you can use following:
Ich erzähle euch jetzt die Geschichte, wie es dazu kam, dass der Kirchturm drei Uhrwerke bekommen hat.
Translation:
Ich will now tell you the story how it came to be that the church spire got three clockworks.
