Replace text when in visual-block mode

Why don't you select 4 columns and hit c?

<C-v>
2j
3l
cDone
<Esc>

Also, you could use :h normal:

V
2j
:'<,'>norm 7lRDone
<Esc>

If you want to substitute within a visual block, you can use the vis.vim plugin.

http://vim.wikia.com/wiki/Applying_substitutes_to_a_visual_block

To install:

Download vis.vba.gz from http://www.drchip.org/astronaut/vim/index.html#VIS

# Open vis.vba.gz in Vim 7.1 or later.
vim vis.vba.gz

# Source the open file.
:so %

# Quit Vim
:q

Once installed:

ctrl-v to enter visual-block mode
Move to select the block you want
:B s/pattern/newtext/

Even better, you can perform any Ex command on the visual block, not just substitutions. For example :B !sort.