Since I saw this question today, I've been fiddling with various Linux Bitcoin Wallets.
Multibit seems to be the best fit for your needs. You can create an arbitrary number of addresses, with labels.
I think it's impossible by definition to have a local wallet without a local blockchain. If you need your wallet's blockchain to be online, you probably need ...
Electrum (License: GPLv3)
uses a remote blockchain (you can choose among several public servers), and
it automatically creates new addresses until a (configurable) gap limit of unused addresses is reached. IIRC, it has the ability to label them, too.
I don’t know if, or to which extent, it integrates with Ubuntu’s notifications, HUD, or Global Menu.