We derive Feynman-Kac formulas for the ultra-violet renormalized Nelson Hamiltonian with a Kato decomposable external potential and for corresponding fiber Hamiltonians in the translation invariant case. We simultaneously treat massive and massless bosons. Furthermore, we present a non-perturbative construction of a renormalized Nelson Hamiltonian in the non-Fock representation defined as the generator of a corresponding Feynman-Kac semi-group. Our novel analysis of the vacuum expectation of the Feynman-Kac integrands shows that, if the external potential and the Pauli-principle are dropped, then the spectrum of the N-particle renormalized Nelson Hamiltonian is bounded from below by some negative universal constant times g⁴N³, for all values of the coupling constant g. A variational argument also yields an upper bound of the same form for large g²N. We further verify that the semi-groups generated by the ultra-violet renormalized Nelson Hamiltonian and its non-Fock version are positivity improving with respect to a natural self-dual cone, if the Pauli principle is ignored. In another application we discuss continuity properties of elements in the range of the semi-group of the renormalized Nelson Hamiltonian.