1) yes on the Kindle- I have no experience on the nook.
2) I get a 3G signal everywhere I go- there's never been a time or location where I haven't been able to pick up a 3g signal... I never understand how people say they get a Wifi signal everywhere, unless they have open-minded neighbors or hang out at libraries or McDonalds all the time...
3) It depends on what version of the Kindle or Nook you're talking about but both are very thin and small. The difference between the two is negligible. Either would suit.
4) .... I can't think of any other devices that have free, no-strings internet access.... maybe an ipod touch if you want to pray to the gods that you can find an open hotspot? You weren't really clear on this point, it depends on what other features you want your device to have.