I'm looking for a way to create a video and photo montage. I want a "messy" arrangement (not a tidy grid layout) where images and video clips fade in, and fade out and/or get overlaid with new ones. Exactly how this would look is flexible, but that's roughly what I'm after. All the media is held in local files (jpg and mp4 files, although the latter could be converted to avi).
I assume I can do this sort of thing with a video editor, with all the media on timelines, but I've found nothing that handles concurrent video clips, or with the sort of positioning I want.
Any suggestions? And I'd like this to run on Linux if at all possible - I rarely use Windows.