「[俺]{おれ}が[話]{はな}していた[男]{おとこ}」 indeed can mean the two different things you listed. (Note that this is an equivalent of the English relative clause. It is NOT a "sentence" as you said that it was.)
As always, the context will tell you which one of the two it means. With this particular phrase, however, it might take more than just a sentence or two as enough context. One might even have to know the whole background story.
As a writer or speaker, there are ways to alter this phrase so that the reader or listener would understand exactly what you mean without any further context but the short relative clause itself.
To mean "the man I was talking to" or "the man who was talking to me", one could say:
「俺と話していた男」 or
「俺と(or が)[一緒]{いっしょ}に話していた男」
Power of particles, it is.
To mean "the man I was talking about", you could say:
「俺がお[前]{まえ}に話をしていた男」 or more naturally,
「この前(or [以前]{いぜん})俺がお前に話をした男」
Note: I used the tough-guy pronoun 「お前」 to go with the 「俺」 which had already been used in the question. No other reasons.
Lastly, I do not understand at all what you mean by "it's pretty clear で is the "missing" particle" regarding the phrase 「あなたが[笑]{わら}ったこの[丘]{おか}」. As far as grammar, nothing is missing in it.
