The state of EU natural gas production:

Italy - peaked in 1995, production falling at a rate of 5 - 6%

Germany - peaked in the '70s, production flat.

Denmark - peaked probably in 2005, official forecast up to 2009 is decrease by about 1%.

Netherlands - peaked on '70s, production essentially flat.

Poland - peaked in '70s, production has been flat at the level of about 4 billion cubic-m/year, but small increase lately.

UK - peaked in 2000, production falling at accelerating rate.

So all EU gas producers have peaked and most of them are quite small - the only really significant are the UK and Netherlands that account for about 80% of the EU domestic production. The total EU production peaked in 2001. The Netherlands have been able to compensate for the falling UK production - but this is clearly not possible in the future. The Netherland could, maybe, boost its production still by about 10 Bcm above the present level, but this cannot offset North Sea depletion.

So, we can see that the EU domestic gas production is going to decrease considerably in the near future. In 20 years time North Sea (UK, Denmark, Germany, Netherlands) will be almost totally depleted. This means that 80 - 90% of the EU domestic gas will be off. This will increase the imports demand considerably. But probably no outside supplier will be able to cover the EU consumption at the present level.

As we know, Norway cannot increase its exports to the EU. Algeria is a big exporter to the EU, but peaked in 1999. Russia and Central Asia will be more important in the future. Here we have the background.  

You are wrong about Norway. The "Ormen Lange" project will come online in 2007 with 20 billion cubic metres pr. year or about a 25% increase most of which will be piped to the UK. I also believe that they have a significant LNG project coming online this year (Snowwhite).
To be exact, Norway can increase its exports to the EU, but only next year. Ormen Lange will be about 10% of the present EU domestic production, so it will not be able to help much in the little longer run. Besides, part of the new production coming online will only replace depleting wells and, if I remember right, part of the production is already sold to the US as LNG. So, if we look only five years forward, Norway doesn't have much ability to help EU by exporting more gas. There is also the nasty example of gas peaking and production decreasing unexpectedly in the UK sector. The same can happen in the Norwegian sector, too. (The new Norwegian production is not really in the North Sea).

Russia will remain crucially important for the EU as a natural gas supplier. Gas prices will inevitabe rise as China gets its pipelines connected to Central Asia and Caspian Region and Russia and LNG exports to the US increase. There is few real alternatives or substitutes for natural gas in Europe in the required scale. Coal has mostly depleted and it is not possible to increase oil use that much. Nuclear would help, but not in short run - and there is the uranium shortage waiting.