The classical Kepler-Coulomb system in 3 dimensions is well known to be 2nd order superintegrable, with a symmetry algebra that closes polynomially under Poisson brackets. This polynomial closure is typical for 2nd order superintegrable systems in 2D and for 2nd order systems in 3D with nondegenerate (4-parameter) potentials. However the degenerate 3-parameter potential for the 3D extended Kepler-Coulomb system (also 2nd order superintegrable) is an exception, as its quadratic symmetry algebra doesn't close polynomially. The 3D 4-parameter potential for the extended Kepler-Coulomb system is not even 2nd order superintegrable. However, Verrier and Evans (2008) showed it was 4th order superintegrable, and Tanoudis and Daskaloyannis (2011) showed that in the quantum case, if a second 4th order symmetry is added to the generators, the double commutators in the symmetry algebra close polynomially. Here, based on the Tremblay, Turbiner and Winternitz construction, we consider an infinite class of classical extended Kepler-Coulomb 3- and 4-parameter systems indexed by a pair of rational numbers (k1,k2) and reducing to the usual systems when k1=k2=1. We show these systems to be superintegrable of arbitrarily high order and work out explicitly the structure of the symmetry algebras determined by the 5 basis generators we have constructed. We demonstrate that the symmetry algebras close rationally; only for systems admitting extra discrete symmetries is polynomial closure achieved. Underlying the structure theory is the existence of raising and lowering constants of the motion, not themselves polynomials in the momenta, that can be employed to construct the polynomial symmetries and their structure relations.