Not all sediments are deposited in water, but water is important in the formation of most sedimentary rocks.
If we're just thinking about the deposition of the sediment, then we don't necessarily need water. Some counterexamples are:
- Aeolian sandstones, such as the Lower Permian Rotliegend sandstone of the North Sea. These are deposited by wind, not water.
- Some types of sedimentary breccia, which are chiefly deposited by gravity, not water.
- Tuff, which are deposited by gravity and wind, not water. They also undergo substantial compaction and lithification with or without water.
But deposited sediment does not a rock make. Once deposited and if buried, most sediment undergoes compaction and diagenesis, eventually lithifying — a fancy word for turning into a rock. Below the water table, the shallow crust is saturated with (mostly) saline water, and processes like dissolution and cementation are necessarily aqueous. So it's fair to say that water is essential in the formation of sedimentary rocks, on Earth anyway.
You were right to be skeptical, by the way; the video is introductory material apparently intended for grade school audience, so you can't treat it like a textbook. And you can't even take a textbook as 'truth', especially when it comes to slippery things like definitions. Sometimes generalizations and simplifications help, sometimes they don't.