I know that there are methods to structurally manipulate held expressions (discussed e.g. here), but I failed to apply those for this particular problem:
(Hold[{3, 4, 5 | 6}] /. (Verbatim@Alternatives)[x__] :> RandomChoice@List@x)
Hold[{3, 4, RandomChoice[{5, 6}]}]
The code should replace any Alternatives in the held expression with an appropriate choice from the alternatives, in this case either 5 or 6, i.e. it should evaluate the replacement.


HoldFirstis not a "held expression" wrapper, it's an attribute. – FJRA Mar 7 '12 at 2:08Holdrather thanHoldFirstorHoldRestorHoldAll(and deleted my previous comment before I saw your explanation) – kguler Mar 7 '12 at 2:14