Kelly
Plenty of phones can do Next G and other brand 3G. Next G is just a brand Telstra put on their 3G offering. Look for dual band 3g or quad band handset.
If you don't want to change SIMs then one of the above 2sim phones or sim splitters would work a treat... in the right handset.