Can 32-bit Linux use all 4 GB of RAM without a PAE kernel?

Yes, you will need to enable PAE to see all 4GB of RAM. Whilst a 32Bit CPU should in theory be able to use up to 4GB of RAM without PAE, the problem with this is that it requires all 32bits of the address bus to use the 4GB, leaving nothing left for things like graphics cards. So with Non PAE systems, you will get less than 4GB. Enabling PAE will get round this.

You would need the PAE enabled kernel to see the 4gb of RAM, yes. Although there is a lot of debate as to seeing the additional memory through hacks like PAE provides any advantage.

Actually Jeff Atwood made a great post about this very issue: Dude where's my RAM

I assume you want to "reclaim" the lost memory that devices use?

Now remember, physical memory is not the same as virtual address space. That is, each individual program will still only be able to use 2GB. However, more of them may be able to run without swapping.

Also remember that PAE addressing takes more page table/page directory bookkeeping, so you lose some memory to that. Probably much less than the devices used to take.