What worked for me was switching to dvorak. With no keycaps to match the layout, I had no option but to memorize it (initially with the help of a cheatsheet on screen). Conveniently, back then, I had no idea how to revert back to qwerty without restarting X after using xmodmap to switch layout, and I'm the type to not restart my session (or computer) except for updates every few months or so.
It also helps a lot doing this "at home" when you've nothing particularly important to do on the computer (running a basic touch typing tutor program for an hour or two and again later in the evening while just chatting away on IRC or such during the day is great because you're typing but have no real pressure). Not during work. It sucks struggling to get things done, and you're very likely to switch back to the old method and that'll just stall progress.
After one day, I had more or less memorized the layout but of course typing was still slow and somewhat frustrating. After a few days, it stopped feeling frustrating but was still a little slow. In a week or two I had reached or surpassed my original qwerty speed. I never used qwerty during that period, it was learn or bust.