Solution to $\frac{d^2x}{dt^2}+\frac{kx}{m}=0$ This is the system of differential equations which describes simple harmonic motion:
$$\frac{d^2x}{dt^2}+\frac{kx}{m}=0$$
$$x(0)=A$$
$$\frac{dx}{dt}\bigg|_{t=0}=0$$

By guessing that $x$ is of the form $A\cos\left(\omega t+\phi\right)$, I can arrive at the solution following solution: $$x=A\cos\left(\sqrt{\frac{k}{m}}\text{ }t\right)$$

My question is, how can you derive this solution without assuming that $x$ is a sinusoidal function? I have not yet taken a formal calculus course, so a simple solution would be appreciated.
As noted in the problem statement, the ODE $m\ddot{x}+k x=0$ describes simple harmonic motion. More precisely, it's the equation of motion of such a system (i.e. Newton's second law).

What's more crucial for the present purpose, however, is not Newton's laws but rather energy conservation. To reveal this, suppose we multiply both sides of the equation of motion by $\dot{x}$ to get 
$$0=m\dot{x}\ddot{x}+k x\dot{x}=mv\frac{dv}{dt}+kx\frac{dx}{dt}=\frac{d}{dt}\left(\frac12 m v^2+\frac12 k x^2\right)$$
from which we conclude that the energy $E=\frac12 mv^2+\frac12 k x^2$ is conserved. For the initial conditions in the problem, we specifically have

$$\frac12 m\left(\frac{dx}{dt}\right)^2+\frac12 k x^2=\frac12 k A^2.$$

Why is energy conservation useful? Because this ODE is separable:

$$t=\int_{A}^{x(t)}\frac{dx}{dx/dt}=-\sqrt{\frac{m}{k}} \int_{A}^{x(t)}\frac{dx}{\sqrt{A^2-x^2}}.$$

(The minus sign is because, if the object starts from rest with $x(0)=A&gt;0$, it will begin moving with a negative velocity. Other such sign issues can be clarified if one is careful.) Either by trig substitution or by using a table of integrals, one obtains
$$t=\sqrt{\frac m k}\cos^{-1} \frac{x(t)}{A}\implies x(t)=A\cos(t\sqrt{k/m}).$$ So it is indeed a sinusoidal motion.
Solution(Partial): $$\frac{d^2x}{dt^2}=-\frac{kx}{m}$$ $$\implies 2\frac{dx}{dt}\frac{d^2x}{dt^2}=-2\frac{dx}{dt}\frac{kx}{m}$$ 
On integrating both sides: 
$$\implies (\frac{dx}{dt})^2=-\frac{2kx^2}{m}+C$$ Using the initial conditions we get: $$C=\frac{2kA^2}{m}$$
$$\implies \frac{dx}{dt}=\sqrt\frac{2k}{m}\sqrt{(A^2-x^2)}$$ I think you can take it from here.