Edit in JSFiddle

var paises = [
        {
            pais: "España",
            ciudades: ["Barcelona", "Madrid", "Valencia"]
        },
        {
            pais: "Francia",
            ciudades: ["París", "Lille", "Nantes"]
        },
        {
            pais: "Perú",
            ciudades: ["Tacna", "Lima", "Cusco"]
        }
    ],
    total = paises.length,
    boton = document.getElementsByTagName("button")[0],
    parrafo = document.getElementsByTagName("p")[0];

boton.addEventListener("click", function(){
    var p = Math.floor(Math.random() * total),
        pTotal = paises[p].ciudades.length,
        c = Math.floor(Math.random() * pTotal);
    
    parrafo.innerHTML = "País: " + paises[p].pais + "<br />";
    parrafo.innerHTML += "Ciudad: " + paises[p].ciudades[c];
}, false);