The one you're not contemplating: that the sea level rises because of melting of ice that's currently over land. As noted in Rodrigo's answer, when sea ice melts there is no change in the water level, and if the ice is made from fresh water then there will be a small change due to the mismatch in densities. However, that ignores the fact that there is a huge quantity of ice in ice caps and glaciers over land, and if that ice melts then it will contribute to a rise in sea levels.

Yes, if an iceberg melts, it will increase the sea level but that increase in sea level is totally negligible. According to this recent article that shows the breaking of Larsen C ice shelf (is considered the largest iceberg crack till date) :

Yes, Sea Levels Will Rise Thanks to the New Iceberg in the Southern Ocean

Scientists estimate that as the ‘iceberg melts, it’ll add about 0.1 millimeters to the total sea level rise. When compared to the rise that NASA and NOAA are already measuring — currently 3.4 millimeters per year — this 0.1 millimeters might seem relatively inconsequential.

If the Larsen C ice shelf, however, was not a shelf — meaning it was on land and not already plopped down in Earth’s ocean — climate scientists like NASA’s Gavin Schmidt estimate the trillion-plus metric tons of ice would have added significantly more water to Earth’s seas, resulting in some 2.8 millimeters of rise. This amounts to over 80 percent of the sea level rise already happening each year.

There is also a graph which shows the level of sea rise with time (also from same article):

This likely means that we’re in for some three feet of sea level rise, at minimum, explains Steve Nerem, the lead of NASA’s Sea Level Change Team:

"Given what we know now about how the ocean expands as it warms and how ice sheets and glaciers are adding water to the seas, it’s pretty certain we are locked into at least 3 feet [0.9 meter] of sea level rise. But we don’t know whether it will happen in 100 years or 200 years.”

It is true that when pure ice melts in pure water, the water level does not rise. However, the oceans are salty and this makes a big difference. When pure water melts into the salty ocean, water level rises. Your latter reasoning is the correct reasoning.

This answer discusses the physics and the mathematical details behind what we observe and then applies the same to the reality.

---

Mathematical Details:

Let the density of ice and water be $rho_{text{ice}}$ and $rho_{text{water}}$ respectively.

The density of ice is lesser than that of water and hence ice floats on water. Part of the ice will be submerged and the rest will stay above the surface.

The submerged part of the ice is responsible for the buoyant force provided by water.

Let the total volume of ice be $V_{text{tot}}$ and the volume of the ice submerged under water be $V_{text{sub}}$.

According to Archimedes principle, the buoyant force provided by water is given by:

$$F_{text{buoy}} = V_{text{sub}} rho_{text{water}} g$$

The weight of the ice is given by: $$F_{text{weight}} = m_{text{ice}}g = rho_{text{ice}} V_{text{tot}} g $$

As the ice floats on water, the buoyant force must balance the weight of the ice.

$$F_{text{buoy}} = F_{text{weight}}$$

$$V_{text{sub}} rho_{text{water}} g = rho_{text{ice}} V_{text{tot}} g$$

$$V_{text{sub}} = V_{text{tot}}frac{rho_{text{ice}}}{rho_{text{water}}} tag{1}$$

After the ice melts, the mass of ice would've turned into liquid water. The density has changed but the mass hasn't.

Let $V_{text{new}}$ be the volume occupied by the ice mass in its water form.

$$m_{text{ice}} = V_{text{tot}} rho_{text{ice}} = V_{text{new}} rho_{text{water}}$$

$$V_{text{new}} = V_{text{tot}}frac{rho_{text{ice}}}{rho_{text{water}}} tag{2}$$

Inferences:

Compare equation $(1)$ with equation $(2)$. You'll notice that $V_{text{new}}$ is exactly equal to $V_{text{sub}}$.

This result can be interpreted as: the volume occupied by the submerged portion is equal to the total volume occupied by the ice in its water form.

To put in a nutshell, the volume under the sea surface hasn't changed due to the melting of ice.

Therefore, melting of ice does not affect the sea level.

What if the ice and water both had dissolved salts?

This in no way alters the equations $(1)$ and $(2)$. Therefore, the previous inference remains valid.

What if the ice is made up of pure water and the sea is salty?

The equations $(1)$ and $(2)$ would change to the equations given below:

$$V_{text{sub}} = V_{text{tot-pure-ice}}frac{rho_{text{ice}}}{rho_{text{water-salty}}} tag{3}$$

$$V_{text{new}} = V_{text{tot-pure-ice}}frac{rho_{text{ice}}}{rho_{text{water-pure}}} tag{4}$$

As salt water is more dense than pure water, $rho_{text{water-pure}}$ is smaller than $rho_{text{water-salty}}$.

Using the previous statement and analyzing the equations, it can be inferred that sea level rises when a pure block of ice melts in a salty sea.

What if the ice is made up of salt water and the sea is pure water?

$$V_{text{sub}} = V_{text{tot-salty-ice}}frac{rho_{text{ice-salty}}}{rho_{text{water-pure}}} tag{5}$$

$$V_{text{new}} = V_{text{tot-salty-ice}}frac{rho_{text{ice-salty}}}{rho_{text{water-salty}}} tag{6}$$

As salt water is more dense than pure water, $rho_{text{water-pure}}$ is smaller than $rho_{text{water-salty}}$.

Using the previous statement and analyzing the equations, it can be inferred that sea level goes down when a salty block of ice melts in a sea made up of pure water.

Conclusions:

1. If an ice made up of pure water melts in an ocean of pure water, the sea level does not change.

2. If an ice made up of pure water melts in an ocean of salty water, the sea level rises.

3. If an ice made up of salty water melts in an ocean of pure water, the sea level goes down.

4. If an ice made up of salty water melts in an ocean of salty water, the sea level does not change.

---

Melting of ice & its relationship with sea level

Out of the 4 cases mentioned in the conclusion of the mathematical details section, only the following are likely scenarios on earth:

1. Pure ice melts into the salty ocean

2. Salty ice melts into the salty ocean

The remaining two cases are quite unlikely because we don't really have pure water (a.k.a fresh water) oceans and seas.

The glacial ice and ice shelves (these are on land) are made up of snow which is frozen pure water. Due to warming climate (climate change!), large chunks of these fresh water reserves break off and floats into the sea. These are called icebergs (these are floating in the sea). Therefore, when these kind of icebergs melt, they cause the sea level to rise.

When salt water begins to freeze, the ice formed contains the dissolved salts. When this salty ice melts into the salty ocean, the sea level does not change.

If you put those two cases together, we can conclude that the sea level can either rise or remain same due to the melting of ice.

---

Significance of melting ice

Sea-level rise is governed by processes that alter the volume of water in the global ocean—primarily thermal expansion of sea water and transfers of water from terrestrial reservoirs, such as land ice and groundwater, to the ocean. The Intergovernmental Panel on Climate Change (IPCC) Fourth Assessment Report found that thermal expansion accounted for about one-quarter of the observed sea-level rise for 1961–2003, melting of land ice accounted for less than half, and changes in land water storage accounted for less than 10 percent (Bindoff et al., 2007). For the last 10 years of that period (1993–2003), the IPCC estimated that thermal expansion and land ice melt each contributed about half to the total sea-level rise. The improved agreement between estimates of the individual contributions and the total sea-level rise for the later time period was attributed to the availability of satellite altimetry data and other global ocean data sets and to better knowledge of the processes causing sea-level rise. Subsequent work has corrected instrument biases, reducing estimates of the thermal expansion contribution to sea-level rise, and recorded increased rates of land ice loss. In the most recent estimate, for 1993–2008, the contribution from land ice increased to 68 percent, the contribution from thermal expansion decreased to 35 percent, and land water storage contributed -3 percent (sea-level fall; Church et al., 2011).

Source: https://www.nap.edu/read/13389/chapter/5

Melting of ice is the largest contributor towards sea level rise.

Additional references for the previous statement:

1. Causes of Sea Level Rise: What the Science Tells Us (2013) - www.ucsusa.org

2. Is sea level rising? - oceanservice.noaa.gov

3. Sea level rise - Contributions - Wikipedia

There are already great answers to this question. This answer is just a slightly intuitive version of Yashas' answer based on this answer to a related question, Why does ice melting not change the water level in a container?

We shall analyse what happens to the water level after the ice melts completely for four different cases, which arise due to the difference in the nature of ice and water:

• Case 1: Ice made of pure water floating on pure water
• Case 2: Ice made of pure water floating on salt water
• Case 3: Ice made of salt water floating on pure water
• Case 4: Ice made of salt water floating on salt water

In the analysis of all the four cases, I've added an intermediate step labelled (c) using an 'imaginary container'. This container is introduced to bring out the reason for the difference in the levels of water in cases 2 and 3. This doesn't make any difference in cases 1 and 4.

In step (b), the imaginary container is added without disturbing the system. Then the ice is allowed to melt within the container. After melting, the level of water inside the imaginary container may or may not be the same as that of the outside. Then, in step (d), the imaginary container is removed. Or, for the sake of simplicity, imagine that the imaginary container alone vanishes by some means. The water which was initially inside the imaginary container now mixes with the water outside and the water level of the beaker attains equilibrium. The horizontal green line represents the initial water level in the beaker. Figure 1 is annotated for the reader's convenience.

First, let's consider case 1, where a piece of ice made of pure water floats on pure water in a beaker. As per the Archimedes' principle, the buoyant force on the ice is equal to the weight of liquid displaced by it. Here, the volume of liquid (water) displaced by the ice is equal to the volume of submerged ice (labelled part 2). Weight of the ice, parts 1 and 2 combined, is equal to the weight of water of volume equal to part 2. When the ice of volume parts 1 and 2 melts, the water obtained occupies only volume equal to that of part 2. This is because of the fact ice is less dense than water. The net result is the water level in the beaker remains the same.

As mentioned in the beginning of the answer, this explanation is based on this answer. Now, let's extend this to other cases. Next on our list is case 2, where a piece of ice made of pure water floats on salt water. We know that salt water is denser than pure water. So the same mass of ice displaces less amount of salt water. Or in other words the submerged volume is less than that of the previous case. The weight of salt water of volume part 2 is equal to the weight of the ice, as per the Archimedes' principle. But, as we allow the ice to melt inside the imaginary container, the water obtained occupies more volume than part 2. This is because pure water is less dense than salt water. This is where the imaginary container helps us to see the difference.

In (c), we can see that the level of water inside the imaginary container is higher than that of the outside. So, when we remove the imaginary container in step (d), the water level in the beaker rises.

Now, let's move on to case 3, where a piece of ice made of salt water floats on pure water. As the ice made of salt water is denser than the ice made of pure water, it displaces more water compared to the pure ice. Again, as per the Archimedes' principle, weight of ice is equal to weight of pure water of volume part 2. But, this time as the ice melts, the salt water obtained occupies a lesser volume than that of part 2.

In (c) we can see that the level of water inside the imaginary container is less than that of the outside. When we remove the imagniary container in step (d), the water level in the beaker drops. The final case in our analysis is a piece of ice made of salt water floating on salt water. This case is very similar to case 1 and the level remains unchanged.

So far we dealt with pieces of ice floating on water in a beaker. Scaling things up, the results obtained here apply to icebergs floating on oceans. As Yashas described, we know from our experience that sea water is salty, and hence only cases 2 and 4 are possible. So, as icebergs melt sea level must either increase or remain the same.

However, the major contributor to the rise in sea level is not due to melting of ice floating on water, but is due to melting of ice on land which is not floating. This is like pouring water in a cup of water. This fact is well explained in Nilay Ghosh's answer.

Apart from the salty/freshwater discussion. If all floating ice (the future for the Northern ice cap looks dim) is melted, less radiation from the Sun is reflected back in the atmosphere. More radiation is absorbed by the water that takes the place of the ice. This on its turn means that the oceans are slightly warmed. Because the average temperature of the surface water on Earth is about 17 degrees Celcius (look here) the water will slightly expand and cause a slightly higher sea level.
More importantly, because the temperature of the water is slightly raised some organisms in the seas and oceans (especially where the water is not too deep), which are very sensitive to the temperature of the water will not have enough time to adapt (evolution is a slow process) and suffer the consequences.

And also, more importantly, is the ice that covers the landmasses. Glaciers are melting and moving at disturbing rates. Water coming from this ice will significantly make the sea level rise.