Simulation of fluid-structure interaction is a complex problem that involves modeling different physics for the fluid and the structure and coupling them together in a stable and efficient manner, and developing scalable numerical methods for this highly nonlinear problem is a computational challenge. Here we develop and test parallel, scalable techniques in the multilevel Newton-Krylov-Schwarz family for solving the nonlinear, monolithically coupled fluid-structure interaction system on dynamic moving finite element meshes in the arbitrary Lagrangian-Eulerian framework. We develop and numerically evaluate parallel nonlinear and linear grid-sequencing techniques and linear multilevel preconditioners for the monolithically coupled problem with fully implicit time-stepping, compare these results to the corresponding one-level algorithm, and present applications of the method to the simulation of blood flow.