If by intuition we could first prove that
\begin{equation}
\dot{\!\!\theta}=\dfrac{\mathrm d \theta}{\mathrm d t}=b \texttt{(constant)}
\tag{01}\label{01}
\end{equation}
then it could be proved easily that the curve is the brachistochrone cycloid. But I don't find a proof either using the Euler-Lagrange formalism or not (as OP wants).
If we want a proof that time minimisation leads to the cycloid curve without using the Euler-Lagrange formalism then we must make use of the elementary proof of Snell's Law due to Feynman and given in my answer here : Why one should follow Snell's law for shortest time?. The proof doesn't use even differential calculus !!!
First note that the Euler-Lagrange formalism gives the result
\begin{equation}
y\left[1+\left(\dfrac{\mathrm d y}{\mathrm d x}\right)^{2}\right]=D=\texttt{constant}\:, \quad D>0
\tag{02}\label{02}
\end{equation}
and this leads to the cycloid curve (with $r=D/2$).
Exactly this constant of the motion is derived from the analogy of the refraction of light in a medium of variable refractive index (in other terms by connection with Snell's Law of refraction).
In the Figure below we see the path of least time from point $\:\mathrm{A}_{0}\:$ to point $\:\mathrm{A}_{4}\:$ through 4 regions of variable speed, increasing towards positive $\:y$. This would be the light path with decreasing refraction index. Under the assumption of least time path $\:\mathrm{A}_{0}\mathrm{A}_{4}\:$ every intermediate path $\:\mathrm{A}_{j}\mathrm{A}_{j+2}\,(j=0,1,2)\:$ is a path of least time between points $\:\mathrm{A}_{j}\:$ and $\:\mathrm{A}_{j+2}\:$. So,
\begin{equation}
\dfrac{v_{1}}{\sin\theta_1}=\dfrac{v_{2}}{\sin\theta_2}=\dfrac{v_{3}}{\sin\theta_3}=\dfrac{v_{4}}{\sin\theta_4}=\textrm{constant}
\tag{03}\label{03}
\end{equation}
Now, if instead of the discrete regions we have a continuum with speed $\:v(y)\:$ being a continuous smooth increasing function of $\:y\:$, then in place of the piece-wise rectilinear path we would have a continuous smooth curve and
\begin{equation}
\dfrac{v(y)}{\sin\theta}=v(y)\sqrt{1+\tan^{2}\theta}=v(y)\sqrt{1+\left(\dfrac{\mathrm{d} y}{\mathrm{d} x}\right)^{2}}=v(y)\sqrt{1+y'^{\,2}}=\textrm{constant}
\tag{04}\label{04}
\end{equation}
In the case of brachistochrone $\:v(y)=\sqrt{2g\,y}\:$ so above equation yields
\begin{equation}
\sqrt{y\left(1+y'^{\,2}\right)}=\textrm{constant}
\tag{05}\label{05}
\end{equation}
and squaring equation \eqref{02}.
It seems that equation \eqref{01} is a result and not a starting point.

$=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!=\!$
ADDENDUM
This is a response to the OP comment :
That's what Bernoulli did back then, I guess. It's just a matter How you recognize that the property derived hold for cycloid.
[OP means the property equation \eqref{02}].
Separating the variables $\:x,y\:$ in equation \eqref{02} we have
\begin{equation}
y \biggl[1+\left(\dfrac{\mathrm{d}y}{\mathrm{d}x} \right)^{2}\biggr]=D \quad \Longrightarrow \quad \mathrm{d}x=\sqrt{\dfrac{y}{D-y}}\;\mathrm{d}y
\tag{A-01}\label{A-01}
\end{equation}
Since the $\:y$-axis is vertical downwards with the motion starting at $\:y=0\:$, then on one hand $\:y\ge 0\:$ and on the other hand $\:y\le D\:$ because of this same equation \eqref{02}, we can set
\begin{equation}
y =D\,\sin^{2}\theta
\tag{A-02}\label{A-02}
\end{equation}
so from \eqref{A-01}
\begin{equation}
\mathrm{d}x=2D\sin^{2}\theta\,\mathrm{d}\theta
\tag{A-03}\label{A-03}
\end{equation}
or
\begin{equation}
x=D \int \limits_{0}^{\theta}\left( 1-\cos2\theta\right)\mathrm{d}\theta
\tag{A-04}\label{A-04}
\end{equation}
that is
\begin{equation}
x=\dfrac{D}{2}\left( 2\theta-\sin 2\theta\right)
\tag{A-05}\label{A-05}
\end{equation}
while equation \eqref{A-02} is written as follows
\begin{equation}
y=\dfrac{D}{2}\left( 1-\cos 2\theta\right)
\tag{A-06}\label{A-06}
\end{equation}
Defining
\begin{equation}
\phi\equiv 2\theta\,, \quad D=2r
\tag{A-07}\label{A-07}
\end{equation}
equations \eqref{A-05},\eqref{A-06} are expressed as
\begin{align}
x\left(\phi\right) & = r\left(\phi-\sin\phi \right)
\tag{A-08a}\label{A-08a}\\
y\left(\phi\right) & = r\left( 1-\cos \phi\right)
\tag{A-08b}\label{A-08b}
\end{align}
the parametric equation of a cycloid, say $\:C\:$, generated by a circle of radius $\:r\:$ rolling without slipping on the $\:x\:$axis, see Figure-A and Figure-B in the question.
The time for the particle to move on the cycloid from a point 1 to a point 2 is
\begin{equation}
\Delta t_{12}=t_{2}-t_{1}=\dfrac{1}{\sqrt{2g}}\int\limits_{1}^{2}\sqrt{\dfrac{1+y'^{\,2}}{y}}\,\mathrm{d}x
\tag{A-09}\label{A-09}
\end{equation}
Taking advantage of the constant expression in equation \eqref{05}, the expression under the integral is
\begin{equation}
\sqrt{\dfrac{1+y'^{\,2}}{y}}\,\mathrm{d}x=\dfrac{\;1\;}{y}\sqrt{y\left(1+y'^{\,2}\right)}\,\mathrm{d}x=\dfrac{\sqrt{D}}{y}\,\mathrm{d}x=\dfrac{\sqrt{2r}}{r\left( 1-\cos \phi\right)}\,r\left( 1-\cos \phi\right)\,\mathrm{d}\phi=\sqrt{2r}\,\mathrm{d}\phi
\nonumber
\end{equation}
so
\begin{equation}
t_{2}-t_{1}=\sqrt{\dfrac{\,r\,}{g}}\, \int\limits_{\!\!\phi_{1}}^{\:\:\:\phi_{2}}\mathrm{d}\phi=\sqrt{\dfrac{\,r\,}{g}}\, \left(\phi_{2}-\phi_{1}\right)
\tag{A-10}\label{A-10}
\end{equation}
If the particle starts moving from rest ($t_1=0,\phi_1=0$) then at any moment $t_2=t$ for the angle $\phi_2=\phi$ we have
\begin{equation}
\phi=\omega \,t \qquad \texttt{where} \quad \omega\stackrel{\texttt{def}}{=\!\!=}\sqrt{\dfrac{g}{r}}
\tag{A-11}\label{A-11}
\end{equation}
From the $\phi-$parametric equations of the cycloid, \eqref{A-08a} and \eqref{A-08b}, we have the $t-$parametric equations of this curve
\begin{align}
x\left(t\right) & = r\left(\omega \,t-\sin\omega \,t \right)
\tag{A-12a}\label{A-12a}\\
y\left(t\right) & = r\left(\:\:1\,-\cos\omega \,t\right)
\tag{A-12b}\label{A-12b}
\end{align}