Have Moscow and Beijing ever been cities under the rule of the same empire? It should have been Mongol Empire, I suppose.
How long has it lasted?
The Mongols occupied Moscow briefly in 1237-1238 (less than a year). Basically only long enough to burn the city. At this time, they also occupied Beijing.
The city was rebuilt over the next century and a half. But a second Mongol attempt to occupy the city was repulsed by Dmitriy Donskoy. Meanwhile, the Ming dynasty had successfully begun a revolt against the Mongols in 1368, which meant that they didn't have Beijing either in 1380.
Kublai Khan could qualify, but the answer depends somewhat on how narrowly one defines rule. One should remember that neither city was a capital when his rule began.
Supreme authority for the Mongol Empire lay in the Great Khan (Khagan), ostensibly elected from the chiefs in council (kurultai). In practice Genghis (Chinggis) Khan divided the empire among his sons and grandsons, with supreme authority to be vested in the khagan.
In the west, his grandson Batu led the Golden Horde against the post-Kievan Rus. In 1237-38 he invaded the polity of Vladimir-Suzdal and razed Moscow, then little more than a trading outpost; it would not begin to prosper until late in the century, under Prince Daniel. In the east, the lands of northern China were already securely under Mongol rule. Genghis had razed the former Jurchen Jin capital of Zhongdu, on the site of modern-day Beijing, in 1215.
In 1264, Kublai Khan defeated his brother Ariq Böke to become the de facto Great Khan, and moved his court from Karakorum to Zhongdu. Over the next several years, he would redevelop it into his grand capital of Dadu (Khanbalikh), proclaimed in 1271 with the founding of the Yuan Dynasty. As Great Khan, he would thus have claimed power over both Moscow and what is now Beijing.
His younger brother Hulagu, who ruled as Il-Khan (subordinate khan) in Southwest Asia, and Batu's son and successor in the Golden Horde, Berke, did not challenge his claim as Great Khan. But neither did they attend the kurultai Kublai Khan called to legitimize his rule. For his part, Kublai was preoccupied with matters in China, both in administration and in invasions of Vietnam and Japan. By his death in 1294, the Golden Horde, Il-Khanate, and Chagatai Khanate in Central Asia more or less functioned independently of the Yuan emperor, and would not be subject to the Great Khan until the reign of Tamerlane.