Commerce shipping by weight and country
I ended up doing 12 rules as @nvahalik suggested. Here's an export of one of them. Doing the others is just a matter of cloning this rule and changing weight, territories and shipping price accordingly

{ "rules_dk_shipping_1_499g" : {
    "LABEL" : "DK shipping (1-499g)",
    "PLUGIN" : "reaction rule",
    "OWNER" : "rules",
    "TAGS" : [ "Commerce Checkout", "Commerce Payment" ],
    "REQUIRES" : [
      "rules",
      "commerce_physical",
      "commerce_order",
      "commerce_line_item",
      "commerce_shipping"
    ],
    "ON" : { "commerce_shipping_calculate_rate" : [] },
    "IF" : [
      { "data_is" : { "data" : [ "commerce-line-item:type" ], "value" : "shipping" } },
      { "data_is" : {
          "data" : [ "commerce-line-item:commerce-shipping-service" ],
          "value" : "by_weight"
        }
      },
      { "entity_has_field" : {
          "entity" : [ "commerce-line-item:order" ],
          "field" : "commerce_customer_shipping"
        }
      },
      { "commerce_physical_rules_order_weight_comparison" : {
          "commerce_order" : [ "commerce-line-item:order" ],
          "operator" : "\u003E=",
          "value" : "1",
          "unit" : "g"
        }
      },
      { "commerce_physical_rules_order_weight_comparison" : {
          "commerce_order" : [ "commerce-line-item:order" ],
          "operator" : "\u003C",
          "value" : "500",
          "unit" : "g"
        }
      },
      { "commerce_order_compare_address" : {
          "commerce_order" : [ "commerce-line-item:order" ],
          "address_field" : "commerce_customer_shipping|commerce_customer_address",
          "address_component" : "country",
          "operator" : "is one of",
          "value" : "DK"
        }
      }
    ],
    "DO" : [
      { "commerce_line_item_unit_price_amount" : {
          "commerce_line_item" : [ "commerce_line_item" ],
          "amount" : "3300",
          "component_name" : "shipping",
          "round_mode" : "0"
        }
      }
    ]
  }
}