Cheap is in limited supply...
KVM: DO 512MB in Singapore and Vultr 768MB in Japan at $5 monthly are the cheapest you'll find and both are relatively stable
OpenVZ- OneAsiaHost has $4 monthly 128MB OVZ in Singapore
36cloud in HongKong: cheap at $5 for 512MB KVM but definitely beta and not stable yet.
Prometeus: open a ticket to see if they have anything (Xen) available in Pune, India ...network in Pune isn't the most stable but by Indian standards it's better than most locations in India.
edit: technically, BeriVDS is in Asia (Tomsk, Siberia) and has 256MB KVM for 128 rubles (about $2.50)