Can FFTW perform the FFT on data which is not uniform in time? I can't seem to find a straight-forward answer to this question anywhere online.
The answer is Non-uniform discrete Fourier transform
You can also find a Python wrapper: pyNFFT.
The generalisations of the NFFT include
NNFFT - nonequispaced in time and frequency fast Fourier transform,
NFCT/NFST - nonequispaced fast (co)sine transform,
NSFFT - nonequispaced sparse fast Fourier transform,
FPT - fast polynomial transform,
NFSFT - nonequispaced fast spherical Fourier transform,
NFSOFT - nonequispaced fast Fourier transform on the rotation group
The NFFT is a C subroutine library for computing the nonequispaced discrete Fourier transform (NDFT) in one or more dimensions, of arbitrary input size, and of complex data. New: A Matlab interface is part of the NFFT3. We believe that our library, which is free software, and based on FFTW (FFTW 3.x) should become the NFFT library of choice for most applications.