The Ecumenical Temple never contains altars for every god.
Altars can be found in the Ecumenical Temple (which randomly contains 6-14 altars), as well as scattered around the Dungeon.
So if you visit the Temple and you don't see the altar you need, keep looking in the dungeon. By the time you reach level 9, you should have found the altar you want, with rare exceptions. Of course, reaching level 9 is no guarantee ...
Since version 0.6.0, altars for every god (except Lugonu, Jiyva, and Beogh) are guaranteed to appear either in the Temple or in the main Dungeon between level 2 and level 9. You can find additional altars in various other locations. Since 0.8, you can also find altars in the main Dungeon at level 1.
Lugonu's altar may be found in the Abyss. Jiyva's altar may found at the entrance to or inside the Slime Pits, and, very rarely, early in the main dungeon. Finally, altars to Beogh can appear in the Orcish Mines, or more rarely in the main dungeon, most commonly near the Mines entrance.