Hmm, let's back up a step - I was thinking you had an offboard USB/TTL Serial adapter, not a USB/RS232 Serial adapter.
DB9s like you pictured usually have RS232 levels on them, with Rx & Tx swinging from -10V to +10V - that will kill the arduino pins.
So, for 1, 2, you need to obtain the correct 0/5V signals.
Something like thishttp://www.nkcelectronics.com/rs232-to-ttl-converter-board-33v232335.html
to interface with your USB/Serial cable
or any of the FTDI breakout board type modules would be more direct.
CP2102 modules are also easy to use - find one of the BAITE modules that has DTR broken out so you can use it software resets during downloads.
Plug in a USB/USB cable, and connect the TTL level signals to your board.
2a. Programming via ICSP header would work (via File:Upload Using Programmer), but not for serial monitor.
If you look at the Duemilanove schematic, you will see resistors between the FTDI chip and the 168 pins for D0, D1. If the FTDI chip is really fouled and interfering with serial operations, then removing those resistors is one way to isolate the FTDI chip. The other way is to cut the traces, or to remove the FTDI chip.