Block bordered systems of nonlinear equations are systems whose Jacobian matrix consists of a series of diagonal blocks, plus a border of possibly dense rows and columns. Large systems of this type occur in many applications in science and engineering, and are attractive candidates for solution on parallel computers. Recently, Zhang, Byrd, and Schnabel developed a new class of algorithms for solving such systems that has significant computational advantages over previous methods on sequential computers, and even greater advantages on parallel computers. Its main feature is that the methods perform multiple inner iterations on the diagonal blocks for each outer iteration on the overall system, in a new way that retains fast local convergence. This paper investigates whether one can develop related algorithms that retain these advantages of parallelizability and fast local convergence, and are also globally convergent and computationally robust on a broad class of problems, including those where the Jacolbian matrix or any diagonal block is singular or ill-conditioned. We introduce related new algorithms for solving such systems, and show that they have strong global convergence properties under very mild assumptions, and retain parallelizability and fast local convergence.