Increase capacitor voltage rating by using multiple capacitors?
You can put capacitors in series, but that rarely works out better than getting the right cap in the first place.  As Steven said, two of the same caps in series have double the voltage rating but half the capacitance.

You also have to be careful that the DC level of the node between the caps is at about 1/2 the voltage.  If one cap has a little more leakage than the other, and this is quite possible, then the mid node won't be near 1/2 way and the voltage rating of one of the caps is exceeded anyway.  One way to deal with this is to put deliberate leakage around each cap that is significantly larger than their actual leakage.  In other words, put a resistor accross each cap.  Make these resistors has high as possible but to still have several times the cap leakage current flowing thru them.  The resistors form a voltage divider that keeps the midpoint at about 1/2 the voltage.

However, all this is a kludge around your original problem.  You want to power something at 5V and you have only a noisy 5V supply available.  Putting a big fat 1 mF cap accross this supply apparently attenuates the noise enough, but there are other ways too.  How much current do the noise-sensitive parts of your circuit draw?  If it's limited to 100 or even 200 mA, then a ferrite "chip inductor" in series with the supply followed by a 20 &micro;F ceramic cap to ground might by all you need.

Probably a all around better approach is to locally make your own 5V from the higher voltage the Arduino also uses for that purpose.  I don't know what voltage the Arduino runs on, but somewhere in your system there must be a higher voltage with some sort of regulator making the 5V the Arduino uses.  That gives you more headroom to drop a little voltage in a filter before your regulator.  The filter removes high frequencies from the higher voltage, and the active electronics in the regulator then deals with the remaining low frequencies.  That should produce a nice clean 5V independent of the Arduino and therefore with none of the Arduino's noise on it.  Another advantage of this is that it doesn't load the Arduino's 5V supply.  I don't know how much extra current capacity that supply has, but probably not a large amount.