You can do it with PHP, but not dynamic. People will have to select United Kingdom first, then press submit, and proceed to select a city.
You can, however, do it dynamic. You can use Ajax to do this properly:
The HTML:
<select name="country" id="country" onchange="getCities(this.value)">
 <option>Brazil</option>
 <option>United Kingdom</option>
</select>
<select name="city" id="city">
 <option disabled selected>Please select a country first</option
</select>
The Javascript:
function getCities(str) {
 if (str=="") {
  document.getElementById("city").innerHTML="";
  return;
 } if(window.XMLHttpRequest) {  // code for IE7+, Firefox, Chrome, Opera, Safari
  xmlhttp=new XMLHttpRequest();
 } else {   // code for IE6, IE5
    xmlhttp=new ActiveXObject("Microsoft.XMLHTTP");
 } xmlhttp.onreadystatechange=function() {
 if(xmlhttp.readyState==4 && xmlhttp.status==200) {
  document.getElementById("hat").innerHTML=xmlhttp.responseText;
 }
}
 xmlhttp.open("GET","getcities.php?q="+str,true);
 xmlhttp.send();
}
In getcities.php you'd get all the relevant cities, and output them as <option>city_name</option.