How to adjust rear brakes on this bicycle? Background

Because I just cannot ask a question without a textwall of unnecessary context. This is my old bike. It's somewhere between 20 and 25 years old; the last 15 of which were spent on my balcony (dry, but outside temperature). It's seen all my teenage years, but not a professional mechanic. Lately we've started cycling in our family, so I've resurrected it. I changed the tires and the tubes (since the old ones were a lost cause), and the next part that is now giving me trouble are the brakes.

The front brakes are kinda OK-ish. When I say "cycling" I mean "slowly cruising between 10 and 20 km/h, because we have a 6 year old kid with us", so for that purpose they are fine. Although I wouldn't expect them to perform any emergency stops. Still, I guess that's just a matter of tuning so I'll just keep on twiddling them until I get them right.

The rear brakes however are so weak as to be basically negligible. And I haven't been able to do anything about it.

The actually relevant stuff

There are several things which have me stumped. Here's an overview. I've marked two points:



At point A the wheel is pretty close to the center between the two metal frame parts, but at point B it's significantly closer to the right side (that is, closer to the camera). Since it's not centered, the left brake pad has to travel much farther than the right. This in turn means that the total distance both pads have to travel together is larger than what my brake lever can do. Hence: not enough pressure to the pads.

Unfortunately, I cannot see how to aligh the wheel along that axis. The only available adjustment is in a direction perpendicular to that which I need.




Then we come to the brake pads themselves. The left brake pad is fine, but the right one is at a significant angle to the rim:



These are new brake pads, by the way, I bought those too since the old ones were really worn out and one was even bent for some reason. But how do I adjust THAT angle? There is nothing there that I can see:



I'm starting to wonder if maybe my frame is subtly bent and all this is a lost cause? Does anyone know how/if it is possible to make my rear brakes work?

P.S. I've been told this is an older type of brake system and I haven't been able to find a video/tutorial that shows how to properly adjust it. If anyone has a link, please share!
It sounds like you've really done some good work! The pad material shouldn't be too soft. Soft enough that it creates good friction when pressed against the rim, but still rigid enough that it holds its shape while doing so. Keep in mind they will break in after using them for a few days or a week or too. The pads you have look like they should be just fine, although it's hard to tell from pics, but Kool Stop pads are my favorites and I know they work great, if you  chose to try something different.