I'll answer your second question first:
Yes, the template you should use for displaying all the custom post types would be the CPT archive, so archive-video.php sounds right.
For the categories (the exact way to say it would be "taxonomy terms" indeed), you would use taxonomy-{taxonomy}.php or even taxonomy-{taxonomy}-{term}.php if you need to get more specific.
About your first question, there is currently no core functionality to use custom taxonomies in your permalinks, but this might help you.