Videos via the video shortcode are always 640px wide?

That width is dictated by the $content_width global, defined by the Theme. To change it, you’ll need to hook into after_setup_theme and modify it:

function wpse124075_setup_theme() {
    global $content_width;
    if ( ! isset( $content_width ) ) {
        $content_width = 640; // your value here, in pixels
    }
}
add_action( 'after_setup_theme', 'wpse124075_setup_theme' );