Don't places without income taxes have higher sales taxes and luxury taxes? (i know that Texas does this, I think)
Not necessarily. I don't have a link, but I think John Lott goes through this in one of his books, showing how removing property tax helps a state's revenues without raising sales tax. Basically, by removing the property tax, your citizens have more money to spend on other things, and sales tax revenues increase without increasing the sales tax rate.
It's up to how you lean politically to decide which model works best, I guess.