To answer the first question: there are two completely elementary proofs of the existence of differentiable good open covers: the first one is Lemma IV.6.9 in Demailly's “Complex Analytic and Differential Geometry” and the second one is Theorem 5.3.2 and Appendix C in Guillemin and Haine's “Differential Forms”. These proofs rely on a fact that star-shaped open subsets of R^n are diffeomorphic to R^n, an an elementary proof of which can be found here: What are the open subsets of $\mathbb{R}^n$ that are diffeomorphic to $\mathbb{R}^n$.
These proofs are similar and the techniques used in them can also be adapted to show the existence of tubular neighborhoods in an elementary fashion, without using Riemannian metrics, although I do not have a reference for such a proof.