Best way to implement variable phase shift on FPGA?
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.