Since Ryan has reawakened this question, let me add a few remarks. One way to get a handle structure on a manifold $M$ is to start with a smooth triangulation of $M$, so I will assume such a triangulation exists. A nice neighborhood of the 0-skeleton then gives a collection of 0-handles. Enlarge this to a nice neighborhood of the 1-skeleton by adding 1-handles. Then enlarge to a nice neighborhood of the 2-skeleton by adding 2-handles, and so on. To a handle structure constructed in this way it's clear one can associate a self-indexing morse function. The handle structure does not quite satisfy all the conditions imposed in the original question since $M_0$, the union of the 0-handles, is not connected, but requiring $M_0$ to be connected would force it to be just a single 0-handle, hence there could only be finitely many 1-handles attached to this 0-handle, then only finitely many 2-handles, etc., forcing $M$ to be compact. This is assuming that $M_0$ is to be obtained from the empty manifold $M_{-1}$ by attaching 0-handles. If $M_{-1}$ is not required to be empty then one could just do the stupid thing of taking $M_{-1}=M$ and attaching no handles at all.
This perhaps reduces the question to the existence of a smooth triangulation. Open sets in Euclidean space certainly have smooth triangulations, for example. If I recall correctly, one proof of the existence of smooth triangulations for closed manifolds involves embedding the manifold in a Euclidean space of high enough dimension, choosing a suitably fine triangulation of this Euclidean space and intersecting the simplices with the manifold and then somehow subdividing the resulting cells into simplices. This should work just as well for noncompact manifolds that have proper embeddings into Euclidean space.
