How was Shlomo Hamelech permitted to place 2 more kruvim in the Beis Hamikdosh, Rashi at the end of Parshas Yisro says it is forbidden like avoda zara!
Rashi on the Torah, as you correctly noted, quotes a Mechilta that says, "You may only have two Keruvin in the Kodesh ha'Kodashim. Making four is prohibited."
However, regarding the construction of the Beis ha'Mikdash, the verse says, "ha'Kol b'Kesav mi'Yad Hash-m" (Divrei ha'Yamim I 28:19), that is to say, every detail of the building of the Beis ha'Mikdash -- including the Keruvim that Shlomo added -- was done with Ru'ach ha'Kodesh and by word of the Navi (Bechoros 17b). For this reason it was permitted to add Keruvim as a "Hora'as Sha'ah," based on the word of a prophet, as TOSFOS points out (54b; see also Hagahos Ya'avetz there and Malbim on the verse you quoted).
I later found that Teshuvos Radbaz (# 2189) asks your question. Aside from pointing out that it was done b'Ruach ha'Kodesh, as above, he explains that since the prophet told Shlomo to build the Keruvim in such a manner, it must be that the Torah only prohibited adding Keruvim on the Kapores , like the original two. Standing Keruvim, with their feet on the ground near the Aron, were permitted.
M. Kornfeld