We can generate the borel sigma algebra by taking an intersection of all the sigma algebras containing the open sets.
This collection is non empty because we can just take the powerset of the real numbers.
But how do we know that the borel sigma algebra is a proper subset of the power set of the real numbers?
On
You don't need the axiom of choice to show that there are subsets of $\mathbb R$ which are not Borel. In fact it can be proved that there are fewer (in terms of cardinality) Borel sets than subsets of $\mathbb R$.
To be precise the set $\mathscr B(\mathbb R)$ formed by all Borel subsets of $\mathbb R$ is equivalent (i.e. there is a bijective function) to $\mathbb R$. See https://math.dartmouth.edu/~m103f17/borel-sets-soln.pdf.
Since there is no bijective function from $\mathbb R$ to the power set of $\mathbb R$, we are done.
Are all sets measurable?
Most anything you can imagine turns out to be measurable. It is a lot of work to find a non-measurable set. The standard example is the Vitali set which is hard to imagine and needs the axiom of choice to construct. In fact we cannot get away from the axiom of choice here. There are set theories without choice where all sets are measurable.