A coin toss would still be subject to the laws of physics. Coin results are not inherently random; if anything, coins are MORE deterministic than the quantum mechanics at the heart of brain function. They're affected by Coriolis effect, wind conditions, initial energy input (the flip), including the exact amount of angular momentum applied and the distance from the ground when the coin is released.
So in that sense, a coin toss would prove that the choice of ice-cream is even more deterministic.
I think it important to note here that free will may well require a non-deterministic mechanism in which to operate but most of the universe would appear to operate on purely deterministic principles. Even quantum mechanics (which many claim has a random element) seems to obey deterministic rules; the Double Slit Experiment for instance always gives a known result based on a probability distribution; NOT a 'slightly random' element as many claim. It should also be noted that the idea that summing the probability distributions of 2x single slits doesn't give the same result as the DSE because it doesn't take into account resonance. If you account for phase of waveform in the SSE results, you'd probably find that the sums DO match (although that would be a VERY hard experiment to perform and the observation requirements would be impossible with current technologies).
Why is all this important? Well, what we're saying is that the Quantum Mechanical functions in the brain are considered a possible source of non-deterministic function; that's more plausible than introducing a coin flip, and even then not by much. The coin flip would only make it WORSE in terms of the application of free will because it removes the choice of the mind and replaces it with a classical Newtonian deterministic function.
If you got Heads and STILL picked strawberry though, you may have the start of a case...