if your tank has fish in it, you should be doing weekly water changes whether you have plants or not. you have to take into account total dissolved solids, nitrate levels, etc.
i have 2.5wpg, no CO2, i JUST started adding Excel about a week ago, no other ferts. i have a slightly overstocked tank on fish, and i do 40% water changes one to two times a week. you can never do too many water changes. that is probably the reason i've been able to get away with not adding ferts, is because i am constantly replenishing the nutrients with water changes, as my tap water is very nutrient-rich.
i don't think ANY tank should go more than a week without a water change. its just not healthy.