The possibility to tailor ferroelectricity by controlling epitaxial strain in thin films and heterostructures of complex metal oxides is well established. Here it is demonstrated that apart from this mechanism, 3D film growth during heteroepitaxy can be used to favor specific domain configurations that lead to step-like polarization switching and a giant nonlinear dielectric response in sub-switching ac electric fields. A combination of cube-on-cube epitaxial growth and the formation of columnar structures during pulsed laser deposition of Pb0.5Sr0.5TiO3 films on La0.5Sr0.5CoO3 bottom electrode layers and MgO (001) substrates stabilizes ferroelectric nanodomains with enhanced dynamic properties. In the Pb0.5Sr0.5TiO3 films, a- and c-oriented epitaxial columns grow from the bottom to the top of the film leading to random polydomain architectures with strong associations between the ferroelectric domains and the nanocolumns. Polarization switching in the two domain populations is initiated at distinctive fields due to domain wall pinning on column boundaries. Moreover, piezoelectric coupling between ferroelectric domains leads to strong interdomain elastic interactions, which result in an enhanced Rayleigh-type dielectric nonlinearity. The growth of epitaxial films with 3D columnar structures opens up new routes towards the engineering of enhanced ferroelectric and electromechanical functions in a broad class of complex oxide materials.