It's only semi-plausible, but if you reduce the impact of the Great Recession with a late POD (in particular, late enough that the Iraq War happens as in OTL), then the EU is in very good position to have something like a common army by 2016, though it probably wouldn't be called that. Recall that pro-EU views were strong in the 2003-6 era - not strong enough for the EU constitution to pass, but strong enough, especially among educated people, that integration was not seen as an awful assault on the national character or whatever. Not all of today's europhobia is induced by the recession, but a lot of it is. In particular, in the mid-2000s, Eastern Europe associated the EU with prosperity, as seen by fast growth rates all over that region, especially in the countries that were most integrated into the European economy, e.g. Poland, Czechia, Slovakia, and Slovenia. This was happening even when Russia was still fairly weak (it wouldn't surpass its 1990 per capita GDP until 2006), although many of those countries were justifiably paranoid about Russia's eventual ambitions. In 2016, a resurgent Russia would make them strongly interested in EU integration to balance against Putin; even with the recession's especial impact on Eastern Europe, the region remains pro-EU and pro-austerity.
The other ingredient needs to be a common enemy for the EU to balance against. It can't be Russia, which barks more than bites. In 2003-6, it was Bush's America, which was ignoring international precedents and launching a war most of Europe opposed; this has been muted later on because of Russia, and because of the election of a US president who Europe does not hate.
So let's set the POD to be 2004. The actual POD is not a single event, but rather a slightly slower housing bubble. The US enters nominal recession in late 2008 rather than late 2007 as in OTL; the financial crisis only hits in late 2009 and not in late 2008 as in OTL. Iraq is a clusterfuck as in OTL, and the core of Europe opposes it as in OTL. The winner of the 2008 US election is Giuliani, chosen because he's both very hawkish and more likely than McCain to shit on the US's allies. In 2009, Giuliani launches a war on Iran; Poland sends troops, but none of the other big European countries does - Blair tries, but faces a vocal insurgency within his party, and as a compromise, the UK announces that it stands shoulder to shoulder with the US but then only provides token support. Meanwhile, in response to the recession, Giuliani starts a trade war with the EU; the EU responds with a combination of its own trade protections, increased economic aid to a handful of hard-hit countries (Greece initially, until it gets cut off for having lied about its budget situation, but mainly Spain and Portugal), a pan-EU infrastructure package including megaprojects across the Alps and the Baltic Sea, and a small amount of social spending to harmonize access to education across the union.
The Arab Spring happens roughly on schedule. The results in Tunisia, Egypt, and Libya are as in OTL. In Syria, Assad relies on Russia from the start; by 2012, Giuliani says that Assad is a crucial ally against Al-Qaida, and praises Putin for being able to put down terrorism. The economy is recovering, very slowly, and after Obama's failed presidential run in 2008 the Democrats are going for experience and nominating Hillary Clinton, who manages to snatch defeat from the jaws of victory and lose by 2%.
By 2013, there's a pan-European nationalism brewing. In this mentality, the EU represents everything that is good in the world: multicultural and equal, in opposition to American racism (but the Roma are all lazy and the Muslims are terrorists, and there's certainly no discrimination against them); multilingual, in opposition to American monolingualism; more egalitarian and social (and any statistic showing fast growth in inequality is just Anglo-American economist fiction); and more concerned with the world, in opposition to American isolationism (except when the Americans bomb and the Europeans don't care either way). The US is as rich as in OTL, or even a hair richer because there's no fiscal tightening in 2011, while the EU is substantially richer than in OTL, growing not far below OTL's 2000-7 trend, and faster than the US from 2007-16. As part of the EU nation-building exercise, an army is formed, separate from the structure of NATO, for peacekeeping operations in Libya. The European elites do this not because any of them cares about peace in Libya, but secondarily to stop the flow of refugees from North Africa, and primarily to prove to the world and to themselves that they can do it.