If I were you, I'd start looking at used bikes. You'll get much better value for your money. Try and find an older mountain bike at a garage sale or a Salvation Army store. Maybe you can find a friend who knows more about bikes to help you? Or someone from a local bike club who might come hunting with you or ask the club members if they have any old but decently built bikes to sell? Look for a steel frame so you can get it welded if it breaks.
I would definitely not go the supermarket route for a bicycle because you'll just end up with total trash.
Although the "easy" way to get set up for touring is to spend lots of money on top notch gear (that's what we did!) you don't have to have a lot to tour, as long as you are prepared to stop and fix things along the way and you may end up buying a few bikes along the way -- possibly an argument to up your budget slightly since you will save in repairs later on. I believe Alastair Humphreys did his RTW trip on four different bikes costing about $400 each.