Proving a decision was randomly made
You're close with the idea of using an envelope; the standard answer is to use a commitment scheme; this is a scheme where someone can publish a 'commitment' to a value, and then later revealing what that value was.  The two essential properties of commitments are:


Someone just looking at the commitment cannot tell what the secret was
Someone with the commitment cannot reveal a value other than the value that was committed to.


How this works in this scenario is exactly analogous to your envelope method; Alice selects a random bit, and publishes a commitment to that bit.  Bob then selects a bit (there's no need for a commitment there) and publishes it; Alice then reveals the bit she committed to; the exclusive-or of Alice and Bob's bit is the output.

Now, there are a number of practical commitment schemes known.  The easiest is to use a cryptographically secure hash function; Alice selects a large random value $A$ and publishes the hash value $hash(A)$.  Bob then selects his bit and publishes it; Alice then publishes $A$ (and they use, say, the lsbit of $A$ is Alice's bit).

Looking at $hash(A)$, Bob gets no information on what the lsbit of $A$ was (assuming Alice selected a sufficiently large bit string).  This is not a formal requirement of cryptographically secure hash functions, but is a reasonable assumption with real hashes (especially if Alice chooses an $A$ which is longer than the hash function output).

And, assuming that we're using a cryptographically secure hash function, Alice cannot decide to reveal a different value $A'$; if she could, that would mean that Alice found a hash collision $hash(A) = hash(A')$, and we assume Alice can't do that.