How to perform a time domain shift in the frequency domain without zero padding
You must zero-pad, whether implementing the delay in the time domain or the frequency domain. (Consider this: by delaying, you are making the signal longer.)

Implementing the delay with the FFT implements a circular shift. If you don't pad and you use the FFT, the data will simply wrap around on itself. (Imagine that if you didn't zero pad and used the FFT with $\tau = NT$, the duration of the record length. Then you would simply get back what you started with, with no delay, because of circular wrapping.) If you want only an integer number of sample delays, do it in the time domain.

If you want a fractional sample delay, you can use the FFT as you describe. It makes no difference mathematically if you implement say a 20.7 sample delay first in time by 20 samples and then in frequency by 0.7 samples, or whether you do it all in frequency by 20.7 samples. Remember—you padded first. Computationally, as you say, this can increase computation time. But you are only increasing the length by a factor of four so computation time with an FFT should increase by a factor of only two. Is this too much? Alternatively, you can do the "bulk" delay in time and the fractional delay in frequency. In the frequency part, you have a couple of choices. First, before doing the bulk time delay, you can do the fractional delay on the original unpadded data and accept the fractional-sample delay wrap-around error at the beginning of the sequence. Second, you can pad your data by only one sample and do the fractional shift with an FFT. If your FFT software accepts only powers-of-two record lengths and your original record length is a power of two, this will likely slow your computation by more than a factor of two because a fast algorithm is not employed. However, most modern FFT packages provide fast algorithms for sequence lengths that can be factored into products of small prime numbers, so adding one data point might not significantly increase computation time.

Some have suggested alternatively using an interpolater for a fractional shift. The FFT is the ideal interpolater—it exactly interpolates bandlimited data when zero padding without adding a delay exponential or when your delay exponential is added. However, cubic splines are outstanding interpolators and should be in your toolbox.