Wordpress - How to reorder billing fields in WooCommerce Checkout template?

Same can be done through functions.php in your (child) theme:

add_filter("woocommerce_checkout_fields", "order_fields");

function order_fields($fields) {

    $order = array(
        "billing_first_name", 
        "billing_last_name", 
        "billing_company", 
        "billing_address_1", 
        "billing_address_2", 
        "billing_postcode", 
        "billing_country", 
        "billing_email", 
        "billing_phone"

    );
    foreach($order as $field)
    {
        $ordered_fields[$field] = $fields["billing"][$field];
    }

    $fields["billing"] = $ordered_fields;
    return $fields;

}

Thanks to Dbranes for the answer.

Replace:

<?php foreach ($checkout->checkout_fields['billing'] as $key => $field) : ?>
<?php woocommerce_form_field( $key, $field, $checkout->get_value( $key ) ); ?>
<?php endforeach; ?>

With:

<?php 
// order the keys for your custom ordering or delete the ones you don't need
$mybillingfields=array(
    "billing_first_name",
    "billing_last_name",
    "billing_company",
    "billing_address_1",
    "billing_address_2",
    "billing_city",
    "billing_state",
    "billing_postcode",
    "billing_country",
    "billing_email",
    "billing_phone",
);
foreach ($mybillingfields as $key) : ?>
<?php woocommerce_form_field( $key, $checkout->checkout_fields['billing'][$key], $checkout->get_value( $key ) ); ?>
<?php endforeach; ?>

You can make a copy into your theme and edit the template that renders the checkout form.

Adapted from the plugin documentation:

Example
To overide the admin order notification, copy: woocommerce/templates/checkout/form-checkout.php
to
yourtheme/woocommerce/checkout/form-checkout.php

[update]

In this file, just before the fields being printed, there's this action hook: do_action('woocommerce_before_checkout_billing_form', $checkout);.

So, it's just a matter of adding this action in the theme's functions.php or in a custom plugin and reordering the fields as the OP shows in his Answer. No need of overriding the template, or yes if further customizations are needed.