You are on the rite track, the table for the cities and zones looks good. There is a problem with the way the weight classes and zones table is setup though. Rather than have columns for 1, 2, 3 with the prices in them you should instead have the columns like this:
weight_class, zone, price
The table will hold the same amount of info but it will have a unique record for each weight class and zone combination. When the rule is created you will have some custom code on your confirm page that will do the following:
The first thing you do is filter a recordset on the user entered city and store the zone for that city in a session variable. Next you will calculate your dimensional weight and store that result in a session variable. Finally you will have another recordset that will search your new weight_zones table that will be filtered on the zone and dimensional weight stored in the session variables. This will give you the shipping cost that you can store in a session variable.
The final part will be to create a shipping charge rule that will apply a flat rate shipping based on the value of this shipping cost session variable.
There is another part of this that needs to be addressed also, is this weight based on a per line item basis, or do you multiply based on the quantity. If you multiply based on the quantity then you should add a new calculated column to your cart for total dimensions. This will multiply the dimensions column you added by the quantity to give you a total dimensions for that item.