Also, my site is hosted on a free host called 000Webhost, so it is sometimes down. Could that affect ranking very much? ...I don't think Google visits my site very often, and Google Webmaster Tools says so too.
This is a pretty significant issue, which you indicated before here as well. If Google can't reach your site, it's not going to be able to index changes to it and might slow down crawling it. You really should consider moving your site to a more reliable web host.
Is it bad to update too frequently?
Generally, updating content frequently will result in your website getting crawled more frequently, so it's definitely not a bad thing to do.
My URLs are nearly the same as before...
If your URLs change, you'll need to 301 redirect them to ones with matching content, and get the new URLs indexed by submitting them in a sitemap.
My page titles and meta descriptions changed in terms of order. They were starting with brand name, and now they are starting with keywords.
That's not necessarily a bad thing either, providing that you're not repeating keywords (i.e., keyword stuffing).
My site also has no backlinks whatsoever
Obtaining some backlinks from authoritative relevant sites would certainly help, but the site needs to be reachable on a consistent basis too.
Do you think my site is Sandboxed?
It's likely not experiencing a Sandbox effect based on what you've described - it probably just hasn't been crawlable, relearned, and updated. I would suggest first fixing your web hosting, doing appropriate 301 redirection, resubmitting new URLs in your sitemap, and finally working on getting some quality backlinks.