Here's the algebra-based proof I've used in a college algebra class. Perpendicular lines are defined as meeting at a right angle. Assume that we know the Pythagorean and distance formulas.
A possible lemma is that slope of a line indicates how much $y$ increases for a 1-unit increase in $x$ on that line. Given that $m = \Delta y / \Delta x$, when $\Delta x = 1$, we have $m = \Delta y / \Delta x = \Delta y / 1 = \Delta y$.
Assume we have two perpendicular lines of defined slope $m _1$ and $m_2$. Call the point of intersection $(x, y)$. Step to the right by $\Delta x = 1$ unit. On one line you'll be at the point $(x+1, y + m_1)$, while on the other you'll be at $(x + 1, y + m_2)$. The three points form a right triangle and we can use the aforementioned formulas.
Call the lengths of the sides of the triangle $a, b, c$. By the distance formula, these lengths are:
$a = \sqrt{ 1^2 + m_1 ^2}$
$b = \sqrt{ 1^2 + m_2 ^2}$
$c = \sqrt{(m_1 - m_2)^2}$
Then by the Pythagorean formula (and the binomial square formula) we get:
$a^2 + b^2 = c^2$
$\implies 1^2 + m_1^2 + 1^2 + m_2^2 = (m_1 - m_2)^2$
$\implies m_1^2 + m_2^2 + 2 = m_1^2 - 2 m_1 m_2 + m_2^2$
$\implies 2 = -2 m_1 m_2$
$\implies -1 = m_1 m_2$
I'm pretty fond of this proof, because it provides an added opportunity to get more practice and experience with the Pythagorean, distance, and binomial-square formulas, which are key topics in this course. (Perhaps the kernel of the idea here is equivalent to James' proof, but more brief?)