Howdy and Welcome....
Talking about engine builds is one of my favorite things to do, for sure. I try to stop short of telling people what they "should" or "shouldn't" do because so much depends on both how you plan to use the car and also your budget. I steer clear of "is it worth it" kinds of questions too because who am I to judge that for someone else?
Ok, so.... I understand you've got a 389, that you aren't concerned about concours original, and the majority of the time it's going to be on the street (as opposed to long hauls on the interstate or at the strip).
Worth the trouble to track down 455 heads? Probably not if you're hunting performance. All Pontiac D-port heads are pretty much the same as far as port shape and how they flow. Larger chamber sizes have the opportunity to help you out on compression ratio, but some of them would be way TOO big for that. If you've got the budget and you're chasing performance, a better solution would be a set of aftermarket aluminum heads. There's much more performance potential there, especially if you have them professionally ported, plus you get the weight savings, the ability to tolerate a little higher compression ratio on the street, and also the hardened valve seats for unleaded fuel. For street use on 91 octane, shoot for a static compression ratio of 9.1:1. If you're careful and have the right parts you CAN get away with more, but it's rarely worth the risk. On my roller cammed 461 the difference between 9.5:1 and 10.0:1 would only be worth about 8 HP. On a max-effort race motor, sure, but no on the street at least not for me. So, how do you get there? That's where it gets fun. You use some combination of piston dish, chamber volume, piston deck clearance height, even head gasket compressed thickness to get the clearance volume (cylinder volume remaining whenever the piston's at TDC) you need. It's not simple though --- there are negative consequences. For example, although you can get there with "fat" gaskets, that also kills your cylinder quench. Quench is what happens with the piston top gets very close to the head. It creates a lot of turbulence that helps keep things nice and mixed, helps prevent hot spots, and promotes combustion efficiency while reducing tendency for detonation. So tight quench is good. To get the clearance volume without losing quench, if you're using dished pistons, you want the dishes to be D-shaped so you get the volume you need but still part of the piston crown gets close enough to the quench pad on the head to get good quench action. I've got an Excel spreadsheet I fixed up for "experimenting" with compression ratio calculations that I can send you, if you like.
No subsitute for cubic inches, so another budget question would be a stroker kit. I built my original 400 into a 461 that way.
Here are the details. 389's and 400's share the same factory stroke length, so you could go that way if you choose. Stroker or not, I do recommend you invest in some good aftermarket forged rods. Rods tend to be the weak link in these motors and you can get a set of good ones for not much more than you'd pay to have the factory rods cleaned up, resized, and recondiitioned.
Cam choice. Lot's of options open to you here in flat or roller, hydraulic or mechanical. If you go "too rowdy" then you'll have to be thinking about shorter gearing and a looser torque converter, plus it won't make enough vacuum for things like power brakes and factory a/c, if that matters. All of that's solvable - again given enough cash. I'm running a solid roller in my car with 3.50's and a 3200-3500 rpm converter. It only makes about 12-13" of idle vacuum though so I converted my power brakes to a hydroboost system and also went with an aftermarket a/c. It used to be that solid cams needed "frequent" valve lash adjustment. With modern parts you should be fine with a couple times a year unless you're running really heavy spring pressures and/or abusing the car.
As far as manifold and carb, if they're in good shape already I wouldn't change them out until after getting the engine together and seeing where you're at with it. The factory pieces were very good to start with. Some tests have shown they out perform most if not all aftermarket manifolds. It's a question that sees heated debate sometimes

If you happen to "trip over" a tripower system, then by all means.....
Most believe it's best to the the interior last and I agree. Same with the convertible top. Paint and body work generates a ton of dust and debris that gets everwhere an on everything.
Most of your braking force is generated by the front brakes, so whether converting to rear disc is 'worth it' or not I think is mostly personal choice. I chose to on my car, but I'd be hard pressed to "prove" it's any better.
I'd send you to my web site for a very long and very boring photo record of my 69 restoration, but my home computer that hosts the site is in the ditch right now...
One more recommendatoin. A really good guy to talk to when planning out your engine is Jim Lehart of Central Virginia Machine at 434 767 9915. He knows TONS and will give you good information, even without you spending money with him. I used his input a LOT when building my 461, and bought most of the parts through him too.
Have fun!
Bear