for Europe Prometeus would be a fine choice, they have recently started offering servers in India(Asia) as well.
Prometeus only offers Xen VPS's in Pune,India but Leapswitch who they colo with in Pune offers KVM VPS's. I used Leapswitch for 5 months (openvz, India) and didn't have any downtime. Their service/reliability/support is very good. Edis offers KVM in Hong Kong. If you want Singapore and can wait a month, Digital Ocean will be launching there in January.
For Europe KVM: Prometeus in Milan, Tilaa in the Netherlands, DotVPS in the UK are all very good. If you want Germany Hetzner's VPS's are KVM (performance when I tried their VPS's was good but not great)