I think you are on the right track here. You will definitely need to have weights specified for the items in order for this to work. You summary of the charge rules based on the region is correct. To do it this way you must have some method to determine which zone it will be shipped to. In your pages you should have some code that will make this determination and store the result in a session variable. You can then alter the charge rule to include another trigger checking the value of this session variable. This is how you will get the two shipping zones part worked out.
Once you have this part in place creating the rules for less than 25kg would be pretty much just like you have said, it will have a flat rate charge.
Once you get these worked out though you will then need to craft the shipping charge rules that would be used if the item is more than 25kg. When you get to this part you will need to do some editing after the fact to get it working properly.
When you actually setup the rules you will do so almost exactly like you have mentioned in your example only you will have an addition trigger for the shipping zone.
