Gregor and the prophecy of Bane did not show up under the free e-books because it isn't free. But it is available as an e-book from Barnes and Noble but not from Kindle Books.
A quick tip in searching for free e-books is to search by price and type in $0.00.
as far as which one to get him? Being a 9 yr old in this day technology I think he was enjoy and would feel more at home with the color touch screen navigation and the finger swiping capabilities of the Nook.
The kindle with it's archaic little joystick navigation I think would make him look at you with the "What will you do for an encore, give me a Commodore 64?"
The navigation of The Kindle is something to be desired in terms of technology, it is very 1980's hand held electronic game feeling to it.
Between the two I think he'll enjoy the color touchscreen alot more..
Also The Nook does have e-pub so he'll be able to check out books from his local library as well. And epub he would have a wider range of stores to choose from without having to convert them.
good luck and I hope this helps