Well it certainly looks like one of the Eucalypts - the commonest one in Europe is Eucalyptus gunnii, though the mature leaves on this one don't look long enough for that variety, if that's what you're showing in the picture. E. gunnii also doesn't have the characteristic scent, unless you actually crush or bruise the leaves, but even then, its not a classic eucalyptus aroma. Does it have rounded leaves at the top of the tree, or where new growth this year has arisen, rather than the more oval ones in the picture? Otherwise, the next most likely variety is Eucalyptus parvula (previously E. parvifolia) the small leaved gum, with reddish stems like the ones in your picture - the leaves on this one are quite variable, but it, too, has mature and juvenile leaves. Eucalyptus perriniana is another one that's similar, but the leaves are usually paired and encircle the stem, and the stems are marked where the leaves spin around the branch before falling. Mature leaves are long and narrow. Eucalyptus dalrympleana is another possibility, even though the bark showing in your pictures doesn't really confirm that at this age. Closer inspection of the tree, the shape of various leaves, coloration of bark and the shape of its crown, might help determine the variety. These trees are not deciduous, but in a north or central European climate in a severe winter, they may well not only drop their leaves, but be killed back to ground level (see your other question for more on pruning).
The brownish spotting could be one of two things, the most likely being the first:-
- Oedema - caused by very wet weather usually, or if grown in very damp climates
- Eucalyptus gall wasp - symptoms more noticeable in spring/early summer.
Both these things look similar, but inspecting with a magnifying glass, the bumps caused by oedema contain water soaked tissue, and the bumps caused by the wasp are hollow at this time of year.