You need to give each place a rank in accordance with its relative order within its own country. You can use a variable to create a temporary rownumber function in MySQL:
SELECT Country, Location, @r:= CASE WHEN Country = @c THEN @r + 1 ELSE 1 END AS RN, @c:= Country AS C2 FROM Countries, (SELECT @r:= 1) r, (SELECT @c:= '') c ORDER BY Country, Location;
This will lead to the conclusion
COUNTRY LOCATION RN C2 AU Melbourne 1 AU AU Sydney 2 AU IN Chennai 1 IN IN Delhi 2 IN JP Tokyo 1 JP JP Yokohama 2 JP US Arkansas 1 US US New Jersey 2 US US Newyork 3 US
Then you can order it by RN and country to get your desired order.
SELECT Location, Country FROM ( SELECT Country, Location, @r:= CASE WHEN Country = @c THEN @r + 1 ELSE 1 END AS RN, @c:= Country AS C2 FROM Countries, (SELECT @r:= 1) r, (SELECT @c:= '') c ORDER BY Country, Location ) c ORDER BY rn, Country DESC;
SQL script example
EDIT
Since you get matching errors, but didn't indicate which matching errors are the only way, I can hope to fix this, use explicit matching for everything:
SELECT Location, Country FROM ( SELECT Country COLLATE utf8_general_ci AS Country, Location COLLATE utf8_general_ci AS Location, @r:= CASE WHEN Country = @c THEN @r + 1 ELSE 1 END AS RN, @c:= Country COLLATE utf8_general_ci AS C2 FROM Countries, (SELECT @r:= 1) r, (SELECT @c:= '' COLLATE utf8_general_ci) c ORDER BY Country, Location ) c ORDER BY rn, Country DESC
SQL FIDDLE