How can an object be at rest without friction?

Friction is a force, and no object can change speed (accelerate/decelerate) without first being acted on by a force. On a frictionless surface (with no other external forces present), there is therefore no force, and so if an object is at rest to start with, it will not start moving.

The same is true, by the way, of a car whose accelerator has been hit. The wheels will turn, but the car won't move! You therefore need friction for the bottom of the wheels to be able to push against the surface, and for the car to be propelled forwards. We normally consider friction to prevent things from slowing down, which can also be true. But it doesn't always stop objects from moving either.