Iterative parallel imaging reconstruction can be very time-consuming for dynamic imaging applications such as functional MRI. GRAPPA is non-iterative but is generally not well-suited for non-Cartesian acquisitions. In this work, we propose a generalization of GRAPPA applicable to arbitrary non-Cartesian readouts. Our non-Cartesian GRAPPA method works by associating a unique kernel with each unsampled (missing) k-space location, and synthesizing non-Cartesian autocalibration (ACS) data by phase-shifts. This approach requires calibrating a very large number of distinct patterns, for which we propose an efficient NUFFT-like algorithm. With this approach we demonstrate fast reconstruction of 3D stack-of-spirals and stack-of-stars images.