Frequency modulation implementation without trig functions
This is what an NCO (Numerically Controlled Oscillator) does. See this post for more details on the implementation and design considerations Numerically Controlled Oscillator (NCO) for phasor implementation? 



By combining this with a D/A converter for an analog output we get what is commonly referred to as a Direct Digital Synthesizer (DDS).

With an NCO you can it you can easily do FM, PM and if you add an amplitude control at the output AM as well! To do FM specifically, you update the Frequency Control Word on each cycle according to the frequency vs time desired. 

Since your question indicated a concern with efficiency; there has been a lot of work done in optimizing this approach to be highly efficient as well in terms of minimizing ROM storage. This includes more obvious approaches such as storing only 1/4 cycle of a sine wave, but also interpolation approaches are very common and other approaches include the Hutchinson Algorithm and Sunderland Algorithm. 

The Hutchinson Algorithm uses a coarse ROM for a major phase step and fine ROM for a smaller increment and makes use of the small angle approximation:

$$\theta =\theta_F+\theta_C$$
$$sin(\theta) = sin(\theta_F)cos(\theta_C)+cos(\theta_F)sin(\theta_C)$$

for small anlge $\theta_F$:

$$sin(\theta) = \theta_Fcos(\theta_C)+ sin(\theta_C)$$

Thanks Hutchinson!

Also if you have time to spare in the implementation (meaning do not require a final update on each cycle), the CORDIC rotator is also quite interesting in terms of highly efficient approaches for implementing an NCO (or any other applications requiring phase rotation or trigonometric solutions).

References on the CORDIC:

Andraka, Ray, “A survey of CORDIC algorithms for FPGA based computers”, Proceedings of the 1998 ACM/SIGDA sixth international sympsosium on Field programmable gate arrays, pp191-200,  1998
Available at  http://www.adraka.com/files/crdcsrvy.pdf

The CORDIC FAQ at dspguru.com  http://dspguru.com/dsp/faqs/cordic

Maharatna, K, “Virtually scaling-free adaptive CORDIC rotator”  IEE Proceedings on Computers and Digital Techniques, 151, (6), 448-456.
Available at http://eprints.soton.ac.uk/263504/

Original foundation work on the CORDIC Algorithm:
Jack E. Volder, "The CORDIC Trigonometric Computing Technique," IRE Transactions on Electronic Computers, Vol. EC-8, pp.330-334, 1959.
John S. Walther, "A Unified Algorithm for Elementary Functions," Spring Joint Computer Conference Proceedings, Vol. 38, pp.379-385, 1971.
D. H. Daggett, "Decimal-Binary Conversion in CORDIC," IRE Transactions on electronic Computers, Vol. EC-8, No. 3, pp. 335-339, 1959.
M. A. Liccardo, "An Interconnect Processor with Emphasis on CORDIC Mode Operation," Masters Thesis EE Dept, University of California at Berkeley, September 1968.
J. E. Volder, "Binary Computation Algorithms for Coordinate Rotation and Function Generation," Convair Report, IAR-1 148, Aeroelectronics Group, June 1956.

en.wikipedia.org/wiki/CORDIC:  Matlab/Octave code for v=cordic(beta,n)