A strange puzzle having two possible solutions

The reason your intuition deceives you is because we often like to forget strategies which depend on the numbering of the coins, and instead think about it in terms of abstract coins, so at each step the devil takes back one coin, and puts in two new ones instead.

The problem is that this description of the problem has different possible outcomes, which depend on the devil, and how much he likes you. Your friend suggests the first case, of a Scrooge McDuck sort of devil. But to understand the difficulty in accepting the solution, let's consider the three cases.

Case I: The cheapskate devil.

The devil has a list of all the coins. At the $k$-th step he removes the coin with the least index which is still in the basket, and puts in the two coins with least indices he haven't used yet. You can see now, that each coin finds itself with the minimal index at some point, so each coin gets removed. And we are left with nothing.

Case II: The compassionate devil.

This devil wants you to be able to afford a cold beer, after suffering through this confusing process. So he decides to leave you with $n$ coins. He lists the coins, and by the $n$-th level he used the first $k$ coins, and now he repeats the previous strategy. Take out the coins with least possible index $>k$, and add two more. At the end, there cannot be any coin of index $>k$ (the same argument as before), but from the first $k$ coins we have exactly $n$ left.

Case III: The benevolent devil.

We start with the basket having the coin indexed as $1$. At each step the devil removes a coin with an odd index, and puts in two coins, one with an odd index and one with an even index. Since no even indexed coin was ever removed, the basket contains an infinite amount of coins.

You can see this is a legal strategy, because at each step he adds a coin with an odd index, to be taken out the next time.

To conclude, this shows that there is really no clear "intuitive" answer to this process, and it depends on the strategy for removing coins. So one cannot really be sure what is the endgame without carefully analyzing that strategy.

(As often happens with infinite things in mathematics...)

Of course, your friend plainly gave the first strategy, so if you follow the mathematics you will see why you'll be left with nothing at all.

This is actually a well known problem called the Ross–Littlewood paradox. The paradox typically, however, does not say anything about the numbering of the coins or which coins are added/removed. In this case it is impossible to say how many coins are left due to what Asaf Karagila said.

In your version, however, it is true that there will be no coins left. There is a very simple proof by contradiction: If there is a coin left in the basket, then the coin has some index k. But we removed coin k on step k. So there must be no coins left in the basket.

Intuitively the answer is ∞ because I added one coin for infinite times.

This intuition attempts to apply a rule of procedure:

After step $k$ there are $k$ coins

therefore

after infinitely many steps there are infinitely many coins.

the correct answer seems to be 0 because every coin numbered k has been removed

This answer responds to the above rule of procedure by saying, "go on then, if you're so clever, what are the numbers on these coins in the basket?"

The intuitive rule of procedure is not tenable. We cannot present an example of a single coin in the basket, let alone infinitely many. Every possible coin can be proved not in the basket after a certain point.

So, we conclude that if we're going to say what happens "after infinitely many steps" of a process, then we need to be very careful what rules of procedure we allow in our reasoning. Otherwise we'll claim the existence of an infinite set that doesn't actually have any elements, and get ourselves in trouble.

This plain-English version of the coins problem more or less cannot be answered, because plain English doesn't provide us with a theory of what happens "after infinitely many steps".

There are interesting mathematical objects such as the Cantor set, where we have to be careful when defining it not to appeal to a flawed intuitive theory of infinite processes.