I know, it's a theorem and therefore there exists no counterexample. Period. But I want to keep trying and failing and understand why it fails. So consider a function on [0,1], where for every x in this interval f(x) is randomly 0 or 1. Now you might say there is no concept of randomness in real analysis.
So I need to explain more. According to Lusin's theorem, we can remove a subset of [0,1] with measure zero and come up with a function that is continuous. Continuity means that if you know the value of f(a), you will gain some information about the values of f(x) in some neighbourhood of a. The function I'm looking for must have the property that knowing f(a) reveals no such information, for any a in [0,1]. How can one show (independently from Lusin's theorem) that no such function exist? Or does it exist but it's not a measurable function?
As already commented, Lusin's theorem doesn't say what you seem to think it says.
One can give a precise construction of your "everywhere random $0$ or $1$" function. In at least two ways:
Let $(X_t)_{t\in[0,1]}$ be an iid family of random variables, uniformly distributed on $\{0,1\}$, and set $f(t)=X_t$.
Or equivalently, if one is concerned about constructing such a large family of iid random variables: Let $X=\{0,1\}^{[0,1]}$, the family of all functions from $[0,1]$ to $\{0,1\}$. Let $P$ be the product measure$$P=\prod_{t\in[0,1]}P_t,$$where each $P_t$ is the uniform probability measure on $\{0,`1\}$.
Of course putting it that way doesn't really help, since constructing the product of an uncountable family of measures is just the same as constructing that large family of random variables. There's a cheat we can use here, brushing all the measure-theoretic problems under the rug of something that everybody believes: Note that $X$ is a compact abelian group, being the product of abelian groups, and let $P$ be the Haar measure on $X$.
One way or another, there is a natural probability measure on the space of all $0-1$ valued functions on $[0,1]$, so we can talk about what such a function does almost surely. And the answer to your question is that $f$ is almost surely not measurable.
(Not that I've proved that, but it's clear at it "can't" be measurable, since the construction has nothing to do with any structure on $[0,1]$ beyond its status as a set with a certain cardinality. Look at it this way: If $\phi:[0,1]\to[0,1]$ is a nonmeasurable bijection then $f$ and $f\circ\phi$ have the same distribution...)