You found the magic phrase, which is indeed "logic level". The key is to find a guaranteed value for Rds(on) when the gate voltage is 4.5V. For example, the NDP6060L:http://www.fairchildsemi.com/ds/ND/NDB6060L.pdf
When searching at Digi-Key our Mouser use search options that limit the search to those MOSFET's which have guaranteed Rds(on) values at 4.5V and you should be finding all the logic-level MOSFET's.
The Gadget Shield
: accelerometer, RGB LED, IR transmit/receive, speaker, microphone, light sensor, potentiometer, pushbuttons