There are few engines that will fit the 58-63 American and 50-55 Nash Rambler body without a lot of cutting (all of those models are practically the same under the hood). There are some problems with keeping the 196 if you intend to drive the car a lot. The first is parts availability on the road. Lose a water pump and you will have to wait three or more days to get a replacement. Most other most likely to break down parts can be handled easier, like the starter or generator (replace the gen with a late model Delco alt and circumvent that problem), but could still take a few days to get the part. They are costly to rebuild, oversize pistons come from Egge Machine and are $50-60 each. The other parts aren't too bad. Heads at 46+ years old are prone to cracking if run hot. They MUST be retorqued every 2-3 years or 12-15K miles, whichever comes first. If not the head bolts work loose, engine runs hot, and head usually cracks. That said, they are good reliable engines when maintained, and near bullet proof due to forged cranks and rods and heavy block casting.
1) Ford small I-6 family. No point in using one of the little 144/170 mills (if you could find one). The 200 has about the same power as the 196. I'd stick a 250 in there! Note that the old 240 and 300 are bigger blocks and won't fit.
2) Late model Ford 2.3/2.5L Ranger fours, the ones where the intake curves over the valve cover. you must use the EFI, but it does just fit.
3) Old Quad 4 (and whatever Chevy called it later). The FWD intake will clear the left side, just! The problem here is that a special $400 bell or trans adapter is needed to convert to rear wheel drive.
You MUST change the transmission with the engine. The Rambler trans won't bolt up to anything but another 196 (or the smaller 173/184 Nash L-head sixes, but who wants to swap in a smaller engine?).
The 64-65 American is a different story. Matt already stated the only problem with it -- the engine bay is a few inches short to use AC. The radiator has to be moved forward and a short shaft CJ-5 (not CJ-7!) 232 water pump and pulley used on a 232 or 258. The 4.0L is short enough to just fit as is, but the fan is an issue. An electric fan would be a tight fit, and the water pump won't accept a fan. Use a Wrangler or Grand Cherokee water pump, and you might need to use a plastic flex fan and short spacer.
Any small block V-8 will fit, take your pick. Factory parts are available for an AMC V-8 (67+), but change the trans with the engine and it's not much harder to put any other small block in.
The AMC six cylinder rear axle WILL take a mild small block with street tires. Loosen the axles nuts and torque them back down to 250-300 ft/lbs (more IS NOT better!!). That needs to be done every 8-12 years. It's the same strength as a GM 7.5"/Ford 8" (ring gear in the AMC is 7-9/16"). Not for constant drag racing, but will hold up for a cruiser that occasionally burns the tires or makes a pass down the strip. The u-joints will be the weak link. You'll have to have a driveshaft made to match the trans.