I have to recommend a combination of mouviciel and jrista's answers.
You want to use a fast lens, which will allow a shorter shutter speed. This is absolutely necessary if you are going to shoot handheld. Since you only have the kit lens, you should certainly go ahead and get the Canon EF 50mm f/1.8 II, which is about the best lens you'll find under $100 US.
You will also (if you have a choice) want to shoot in the first hour past sunset or the hour before sunrise for the best lighting. During these times there is more light, but you still have the nighttime feel.
Beyond that, go ahead and bump up the ISO. This will cause more noise, but you will want to take that hit to get the higher shutter speed you need to get a clean shot. Also, ISO noise can be dealt with in post, whereas camera shake can't be fixed. Also, take a look into different hand-holding techniques.