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 andTo answer the techniques used in them can also be adapted to showsecond question: for an elementary proof of the existence of of tubular neighborhoods in an elementary fashion, without using Riemannian metrics, although I do not have a reference for such a proofsee Theorem 4.5.2 in Hirsch's “Differential Topology”.