well that depends if you want to start right away...or give yourself a lag year to apply and not have anything to worry about while you are applying outside of work/research etc...
im an advocate of taking a year off at least so i would say submit your AMCAS application in June 2005 to get accepted for the fall of 2006.
as for cheapest schools...before you worry about that since most schools for you will be very expensive...i would worry about which schools are receptive to international students because there are a good number of schools that just dont even interview or accept international students/applications.
if you do a search on sdn about international students, i think you will be able to find some more information. someone who talks a bit about the process is the sdn member Calbee. Maybe he will read this and give you some more information than the limited knowledge i have to give you.