Two B737 aircraft were tracking south on air route A464 at FL330, initially having a 10 minute separation standard, which reduced to 8 minutes before an RNAV distance standard could be achieved. Both aircraft then required diversion left of track to avoid weather, and as an RNAV distance separation standard could no longer be applied, a minimum separation of 10 minutes, or a change of cruising level for one aircraft was now required. Descent to Flight Level(FL)310 was not available due to crossing traffic, and neither aircraft could accept FL350. A decision was made to descend the second aircraft to FL290, requiring the traffic on the crossing route to descend to FL280. Co-ordination of all possible separation methods with Brisbane Control required some time, especially as they were experiencing high workloads. The actual separation of the aircraft was continually monitored, and never less than 105km. As the lead aircraft had only been 8 minutes ahead of the other, a breakdown of separation occurred until vertical separation could be achieved.