There is growing interest in learning Fourier domain sampling strategies (particularly for magnetic resonance imaging, MRI) using optimization approaches. For non-Cartesian sampling, the system models typically involve non-uniform fast Fourier transform (NUFFT) operations. Commonly used NUFFT algorithms contain frequency domain interpolation, which is not differentiable with respect to the sampling pattern, complicating the use of gradient methods. This paper describes an efficient and accurate approach for computing approximate gradients involving NUFFTs. Multiple numerical experiments validate the improved accuracy and efficiency of the proposed approximation. As an application to computational imaging, the NUFFT Jacobians were used to optimize non-Cartesian MRI sampling trajectories via data-driven stochastic optimization. Specifically, the sampling patterns were learned with respect to various model-based image reconstruction (MBIR) algorithms. The proposed approach enables sampling optimization for image sizes that are infeasible with standard auto-differentiation methods due to memory limits. The synergistic acquisition and reconstruction design leads to remarkably improved image quality. In fact, we show that model-based image reconstruction methods with suitably optimized imaging parameters can perform nearly as well as CNN-based methods.