Well, I am in Canada and have done this with an eMate battery pack. You would be best getting some tabbed NiMh AA cells, and following the excellent instructions online at
http://www.pda-soft.de/emate_battery_pack.html . I sourced my NiMh cells on eBay from the US, as I could not find them readily elsewhere. If you are in a large centre, you could most likely manage to source some locally, but I think I bought 20-24 cells for around $50 shipped, which is not bad. The cells then went into various machines — Duos and a 540c — as well as a couple of eMates, so the money was well spent.
The eMate would be by some margin the easiest one to begin with, as there is a lot more room internally and less of a plastic cover to fret about. I have not tried to re-cell my MP2100, as I prefer to use Alkalines, which typically last me 5 months, but Alkalines, while possible with some modifications in an eMate, are not so conveniently used there because of the nature of the machine.
I am no electronics genius - this is an easy fix, especially with the web-based instructions above. The soldering equipment can be bought for $10-15 at The Source, or borrowed for an afternoon from someone or other.
(I was in la Ville de Québec only 10 days ago.)