Start by just having normal 'required' flair on both the fields. Perhaps a colored background. Perhaps colored asterisks.

download bmml source – Wireframes created with Balsamiq Mockups
When the fields get focus, remove the standard flair, and replace it with a specific explanation that only one is required. In my example, I keep the required flair on the active field to reinforce the text that at least one is still required.

download bmml source
To avoid clutter, the brace and explanation only need to appear when those fields have focus, and can replace general 'Required' field flair. While it does not remove the need for 'One of these fields is required', it clutters the form only when strictly necessary, and only temporarily.
When the user finishes with one or both of the fields, the flair adapts to whichever fields are currently filled in, so as not to confuse the user thinking they have to return to fill in an empty field.

download bmml source
I have never needed to require a field in this manner, so this has not been tested by me. I believe it provides good usability for a unique workflow, but I could well be wrong. Always test with real users before using a completely new interface design.