The army thing is difficult indeed. The entire sequence on Kamino is built around the 'mystery', and cutting that, would leave next to nothing.
How I would try to make it fit: by the time AOTC starts, the clone army has already been commissioned, and is well known. The vote Amidala returns to Coruscant for is about whether or not stationing these troops on Republic worlds. This would leave the main plot beats in tact, but would also make the Jedi seem less dense for trusting the army. It would also make the reveal of Order 66 make more impact.
As for showing the army on Kamino, which is necessary because that's what the entire story is about, have Obi-Wan be on a routine inspection to Kamino. Have on character refer to Obi-Wan's mission on Kamino, then cut to Kamino. Introduce the planet using a montage (kind of like how Mustafar is first introduced in ROTS), then cut to Obi-Wan taking the tour, and cutting out the obvious parts. His leaving the planet can be kept as is.