A small US based startup is looking to hire me as a fulltime employee. I am an Indian citizen living in India and will work from India only. Can such a setup work or will I have to work as a contractor/consultant for the US company? If I can be hired where will I have to pay my taxes?

Yes, you can be hired by and work for a U.S. company and work in India. You will be subject ONLY to India taxes for that work as specified under the U.S.-India tax treaty.