First of all: Embedding videos into HTML pages seems to be one of the most complicated things there are. Netscape introduced the embed-tag with theit Navigator 2.0 but it never became part of the html standard.
There are several reasons that make Flash Video the best choice for the video encoding: The quality is good enough for most purposes and the flash plugin is the most common. Every other method is limited to an operating system (wmv -> Windows) or to rarer plugins (Real, Quicktime aso.) Jeroen Wijering wrote a nice article about Flash Video.
Jeroen Wijering not only wrote an article about FLV he also wrote the Flash Video Player which can be used to embed the videos into your site.
I use Pagesetter to store the metadata. My publication type has three fields: title, description and filename. Filename is im my case also a string because the videos are too big to upload them via HTML forms. We upload them into a predefined directory and only enter the filename into the form field.
The flashplayer is stored inside the themes folder:
The -list.html-template of the publication type looks something like this:
I think this is a basis that should allow you to build your own video publication type. It's not too complicated and it works on several platforms and with several browsers.