Let $d(x) = f(x)g(x)$. Then:
$$d'(x) = \lim_{h \to 0} \frac{d(x+h) - d(x)}{h}$$
$$d'(x) = \lim_{h \to 0} \frac{f(x+h)g(x+h) - f(x)g(x)}{h}$$
$$d'(x) = \lim_{h \to 0} \frac{f(x+h)g(x+h) - f(x+h)g(x) + f(x+h)g(x) - f(x)g(x)}{h}$$
$$d'(x) = \lim_{h \to 0} \frac{f(x+h)(g(x+h) - g(x)) + g(x)(f(x+h) - f(x))}{h}$$
$$d'(x) = \lim_{h \to 0} \frac{f(x+h)(g(x+h) - g(x))}{h} + \lim_{h \to 0}\frac{g(x)(f(x+h) - f(x))}{h}$$
$$d'(x) = \lim_{h \to 0} f(x+h)\frac{g(x+h) - g(x)}{h} + \lim_{h \to 0}g(x)\frac{f(x+h) - f(x)}{h}$$
$$d'(x) = f(x)g'(x) + g(x)f'(x)$$
It seems to be right but I only got here because I knew there was some slick "closed-form" ahead of time and I was just trying to figure out how to get there.
When this rule was invented (many years ago, historically speaking), how did they get to the end state without necessarily knowing how it was going to end?
It makes sense to ask "What is the derivative of the product of two functions?" but then it's very easy to get stuck at this step:
$$d'(x) = \lim_{h \to 0} \frac{f(x+h)g(x+h) - f(x)g(x)}{h}$$
Before realizing you can add/subtract the same quantity and do some clever rearranging. How did anyone figure this out? Was there evidence this was a good way to go or did someone just trial-and-error it until they discovered it?
The proof you presented does look bulky but if you use the notation of differentials as Leibniz did, it becomes far more readable. Even Leibniz did not discover the "Leibniz rule" immediately and was for a short time toying with the idea that the differential of a product might be the product of the differentials, but he quickly got the correct result as follows: $(u+du)(v+dv)-uv=udv+vdu+(du\,dv)$ but the term in parentheses is negligible compared to earlier terms because it is "second order" small, and what remains is $udv+vdu$. Leibniz was working with a generalized relation of equality "up to" a negligible term, and there was no logical fallacy in his reasoning; see this 2017 publication in Journal of General Philosophy of Science for details.