How can I schedule adding a new field collection item for all users?
I'm not sure about rules but you could do that in a custom module with a little code:

$uids = db_query("SELECT uid FROM {users} WHERE status=1")-&gt;fetchCol();
$accounts = user_load_multiple($uids);
foreach($accounts as $account) {
    $edit['my_field'][LANGUAGE_NONE]['0']['value'] = 'my new value';
    user_save($account, $edit);
}