Faits: A. C._ travaillait comme encadreur d'art à titre indépendant. Le 3 mars 2004, il a subi une hémicolectomie gauche, puis suivi une chimiothérapie d'avril à juillet 2004 à cause d'un cancer. Le 18 juin 2004, il a présenté une requête de prestations de l'assurance-invalidité. L'Office de l'assurance-invalidité du canton de Neuchâtel (ci-après: OAI) a recueilli deux rapports des 13 juillet 2004 et 4 avril 2005 de la doctoresse M._, médecin traitant de l'assuré, selon lesquels C._ était incapable de travailler depuis le 1er mars 2004. Dans un rapport du 24 mai 2005, la doctoresse S._, médecin adjoint de l'Hôpital X._, a diagnostiqué un adénocarcinome moyennement différencié du côlon gauche avec métastases ganglionnaires et métastase hépathique unique, ainsi qu'un état dépressif réactionnel. Elle a exclu la reprise de l'activité d'encadreur, ce travail nécessitant de la force et de la précision, ce qui était en contradiction avec la neuropathie de l'assuré. A la demande de l'OAI, le docteur E._, spécialiste en médecine interne, a examiné l'assuré et conclu à l'absence de toute limitation significative, ainsi qu'à une capacité entière de travail comme encadreur dès le 1er novembre 2004, avec une possible diminution de rendement ne dépassant pas 20 % (rapport du 6 décembre 2006). Se fondant sur cette appréciation, l'OAI a rejeté la demande de l'assuré par décision du 7 avril 2006. C._ s'étant opposé à cette décision, l'administration a maintenu sa position par décision sur opposition du 25 juin 2007. B. Saisi d'un recours formé par l'intéressé, le Tribunal administratif du canton de Neuchâtel l'a rejeté par jugement du 26 juin 2009. C. C._ interjette un recours en matière de droit public contre ce jugement, dont il demande l'annulation. En substance, il conclut à titre principal à l'octroi d'une rente entière d'invalidité et, subsidiairement, au renvoi de la cause au Tribunal administratif neuchâtelois pour instruction complémentaire sous la forme d'une expertise médicale. Il sollicite, par ailleurs, le bénéfice de l'assistance judiciaire. L'Office fédéral des assurances sociales et l'OAI ont tous deux renoncé à se déterminer.