There's a brief note in this book on how Khayyam bumped into having to solve a cubic.
I'll only make the note that you should remember the context of the time: there was no concept of negative, much less complex, solutions. Corresponding to our current Cartesian system, Khayyam only looked at intersections in the first quadrant.
Another note should be made that the curves of the time were constructed with geometric tools (straightedge, compass, and a bunch of other contraptions), and $y=x^3$ isn't really a sort of curve that easily lends itself to such a construction (but is now easily constructed thanks to our current knowledge of coordinate geometry).
Here is a more explicit mention of the hyperbola-circle intersection problem Khayyam studied and was mentioned in the OP.
Here is a (more or less) complete table of all the intersection cases Khayyam studied. (The book has an appendix containing a (translated) section of Khayyam's work.)
Here is yet another reference.
(I'll keep updating this answer as I comb through more books; watch this space! As an aside, it's funny that my attempts to look for answers to this question are leading me to references for this question!)
I would like to prove the Quadratic Formula in a cleaner way. Perhaps if teachers see this approach they will be less reluctant to prove the Quadratic Formula.
Added: I have recently learned from the book Sources in the Development of Mathematics: Series and Products from the Fifteenth to the Twenty-first Century (Ranjan Roy) that the method described below was used by the ninth century mathematician Sridhara. (I highly recommend Roy's book, which is much broader in its coverage than the title would suggest.)
We want to solve the equation
$$ax^2+bx+c=0,$$
where $a \ne 0$. The usual argument starts by dividing by $a$. That is a strategic error, division is ugly, and produces formulas that are unpleasant to typeset.
Instead, multiply both sides by $4a$. We obtain the equivalent equation
$$4a^2x^2 +4abx+4ac=0.\tag{1}$$
Note that $4a^2x^2+4abx$ is almost the square of $2ax+b$. More precisely,
$$4a^2x^2+4abx=(2ax+b)^2-b^2.$$
So our equation can be rewritten as
$$(2ax+b)^2 -b^2+4ac=0 \tag{2}$$
or equivalently
$$(2ax+b)^2=b^2-4ac. \tag{3}$$
Now it's all over. We find that
$$2ax+b=\pm\sqrt{b^2-4ac} \tag{4}$$
and therefore
$$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}. \tag{5}$$
No fractions until the very end!
Added: I have tried to show that initial division by $a$, when followed by a completing the square procedure, is not a simplest strategy. One might remark additionally that if we first divide by $a$, we end up needing a couple of additional "algebra" steps to partly undo the division in order to give the solutions their traditional form.
Division by $a$ is definitely a right beginning if it is followed by an argument that develops the connection between the coefficients and the sum and product of the roots. Ideally, each type of proof should be presented, since each connects to an important family of ideas. And a twice proved theorem is twice as true.
Best Answer
This is Lill's method for general (real) polynomial roots. After drawing the line segments you cast a ray from the isolated endpoint of the line segment corresponding to the highest-power term, turning $90^\circ$ at (the extension of) each segment corresponding to the polynomial's remaining terms, according to the following rules:
If this ray eventually hits the other endpoint after all the turns, the slope of the initial ray (before its first turn) corresponds to a root of the polynomial.