Inside dyne:bolic you'll find Cinelerra, which implements a common approach to non-linear editing, with a nice user interface, speed and responsiveness.
You can be introduced to Cinelerra by the manual available on manual.cinelerra.org or this online tutorial.
Also AviDeMux is a useful tool for quickly cutting video, supports even more input formats than Cinelerra and can be used to convert between some formats and do simple editing tasks.
Consider that video editing tasks are the most demanding, so you'll need a relatively fast computer (from 2004-2005) in order to achieve decent interactivity and satisfactory results.
For converting between video formats its included the powerful Transcode tool, which is a commandline application that can be scripted to convert large number of files or easily accessed via a graphical interface.