<?php

// input
$cities = array (
    'Lviv'          =>  array('UA', 11111), // even before Huston
    'New York'      =>  array('US', 8175133), // 4
    'Los Andeles'   =>  array('California', 3792621), // 3
    'Chicago'       =>  array('Illinois', 2695598 ), // 2
    'Huston'        =>  array('Texas', 2100263), // 1
);

function custom_sort($a, $b) {
    global $cities_values;

    return $cities_values[$a][1] > $cities_values[$b][1];
}

foreach ($cities as $key => $value) {
    $cities_with_keys[] = $key;
}

$cities_values = array_values($cities);

uksort($cities_values, 'custom_sort');

foreach ($cities_values as $key => $value) {
    echo $cities_with_keys[$key] . ' => ';
}