So the miner has to look up all the blocks form block 1 to the end, which has over 500,000 blocks (and will grow even bigger), for each transaction. And a block contains thousand of transactions. This sounds impossible to me.
No, it just maintains a set of all unspent outputs. For each output in each transaction in a block, an entry is added to that set. For every input, one is removed.
It doesn't need to go through the entirety of history for each input; it just looks it up in the database.
Also, this is not restricted to miners. Every node performs this operation. Miners are only kept honest by the rest of the ecosystem verifying that the blocks they produce are valid.
"A node maintains a list of all unspent transaction outputs." This request each node to maintain billions of address and their unspent transaction outputs. Is this even possible
No, addresses aren't relevant here. The UTXO set is just a set of UTXOs. Each UTXO has an address (or more precisely a scriptPubKey or locking script), but they are identified by the transaction that created them and the position within that transaction.
Every transaction refers to actual UTXOs being spent (by listing the txid and index of the transaction that created them). They're not looked up by address.
The address (script) is only involved in determining whether a particular spend was authorized, by runni g the script with the signatures provided in the input, and checking it evaluates to True.
At the time of writing (July 2018) there are about 49 million entries in the UTXO set. For many systems the entire set easily fits in memory.
You are correct in being concerned about the future though. There are no real incentives in the system to keep this set small, and its growth is effectively unbounded.
There is research into moving to models where nodes don't actually maintain this set themselves anymore, but transactions instead contain proofs that the UTXOs being spent exist and aren't spent yet. Useful search keywords are Bram Cohen's bitset model or Peter Todd's Merkle mountain ranges.