The allpass you're describing is a multiplication with multiple numbers. Hence, if you want to shift your phase, the only mathematically viable and easiest way is indeed a multiplication with $e^{i\phi}$.
I don't see why that would be overly slow – in a modern FPGA, you'd probably utilize DSP slices to do the (real-valued) two multiplications and additions that make up a complex $\cdot$ complex multiplication.
Now, if you need to increment your phase, so you need to *calculate the value of $e^{i\phi}$ first, then there might be room for optimization. In fact, digital tuning happens in FPGAs, in the DSP chains of software defined radio devices like the Ettus USRP series.
There, a pretty standard CORDIC algorithm was employed to approximate a complex sinusoid $e^{i2\pi f}$ of arbitrary relative frequency $f$. Have a look at the USRP X3xx's GPL-licensed RX DSP DDC chain:
cordic_z24 #(.bitwidth(cwidth))
cordic(.clock(clk), .reset(rst), .enable(run),
.xi(to_cordic_i),. yi(to_cordic_q), .zi(phase[31:32-zwidth]),
.xo(i_cordic),.yo(q_cordic),.zo() );
The cordic_z24
is really just a multi-stage CORDIC implementation with pre-computed atan coefficients.
It runs at complex 64MS/s even on 2005 Spartan FPGAs, and doesn't really blink much of an eye about 200MS/s on modern Kintex7 FPGAs.
It avoids explicit multiplication alltogether.