What's the cheapest android device I can get that would still be useful for this?
The Huawei Y210 can be had for $49 around here, and that includes $10 worth of phone calls. As a phone, it's not too flash but probably no worse than an iPhone and, at that price, there is no obligation to use it as such. It works perfectly with the HC-06.
There is some background here which might be useful.http://homepages.ihug.com.au/~npyner/Arduino/GUIDE_2BT.pdf
Note that, while Android is clearly the only way to fly, and I have absolute confidence in the Huawei, I now see that some try-before-you-buy might be in order.
One of the reasons for buying the Huawei is that I despaired of ever getting my clunky Kogan 10.1" tablet to work with any bluetooth device. I normally use an HC-06 but had occasion to use an HC-05 last night and found that it would pair OK with the Kogan. It is now beautifully displaying three graphs with Bluetooth Terminal. It still won't work with the HC-06, and I have no idea why, so I wouldn't recommend it to anybody even though, for my purposes, it is far superior to the phone.