There's two features I'd personally like to see.
1. More complex room generation, to create natural looking floors. You could build a floor using cellular automata + a markov chain created from existing game maps. I used this technique to create a world map generator for FF6; see the attached images. I wasn't planning to do this for FF4, but I was going to use the existing game maps (like in FF6 AC) which I like better than simple maze generation.
2. Branching paths and exploration, and reasons to go exploring. In FF6 AC I hid "rest stops" throughout the dungeon, where the player could shop, sleep at an inn, save, and pick up new espers or party members. Exploration is the aspect that most appeals to me about procedurally generated games... I'm not so much a hack 'n slash guy. It's also the reason I'd like to see more natural-looking floors, because I feel like having easily recognizable landmarks adds a lot to the experience... maybe even more so if they're maps from the game.
If you decide to keep this project as a linear dungeon crawl (it's fine if you want to), then I might go ahead and make my original idea.
Also I'd like to see the characters stay more on the vanilla side of things, or at least leave it as an option. Finishing the game with Dark Knight Cecil dragging your party down is its own kind of challenge.
Your brand of randomization is normally taking Everything that can be randomized and having that option there. For instance Dark Knight Palom might have White/Kick/Regen for his special commands, being able to equip Whips, Hammers, and Harps. This looks to more so be about setting up a normal...ish game as far as setup goes with an Ancient Cave-esque feel, I think the room generation is so simple currently just as a proof of concept, rather than meant to represent the final project. Therefore your goals are already quite different (if I'm getting your MO right, I may be mischaracterizing it) and you should progress with your project (also that FFVI randomized world map idea is awesome, I would love to see that added to Beyond Chaos at some point). However I think what you find and the way you go about randomization may still be of worth to PinkPuff so I strongly suggest the sharing of info. between you two.
Can we hijack a spell routine to do some kind of damage formula based on Level? Level, magic stats, some math = dmg?
Oh yes, that won't be that difficult. I've noted used and unused routines before. I suggest using either Dispel's routine (useless piece of broken garbage... Black Hole does it right), Damage, Status (Unused?), or Rydia Returns. Since Rydia will not be returning so that is not necessary.
Chakra was %CurHP, but there is a routine for healing based on caster's max hp. I think it's 1/10 by default but was there ever a patch made to make that amount variable by spell power?
I thought I made a spell power variant of that...? Hmm, maybe Chillyfeez did? In any case, it's very simple, may not even need any extra bytes for it.
"Scarmiglione: Was it Tremor? I will show you how!" LOL
Reducing the shurikens attack power should probably do the trick. We can play it by ear and tweak as we go. The Ninjutsu moves... I'm not sure... I almost feel like they can either be cut completely or at least be a set of unique utility effects, more along the lines of Pin/Smoke/Image than Flame/Flood/Blitz; especially since anyone can just toss out attack items.
Heh, yeah... You bring up a good point, it does make Edge seem redundant, focusing on more of the unique utility seems like a good idea (though Smoke, just like Exit doesn't serve much purpose other than not losing money when running away).
Also Chillyfeez when you do post the patch for Salve in a menu (I would Love to know how you accomplished that, by the way) let me know what room it takes up so none of our hacks for this step on one another.
The "how" is explained here, in a conversation I was having with... evil Grimoire LD, I guess 
Anyway, the affected data in this patch is as follows (all offsets are ROM w/o header)...
Used Empty Space:
11AB7-11ABB ($5 bytes)
11AC3-11AC7 ($5 bytes)
A0D80-A0DBD ($3E bytes)
Altered Assembly:
13606-13608 ($3 bytes)
139BA-139BC ($3 bytes)
1A6AD-1A6AE ($2 bytes)
1CA6C-1CA6E ($3 bytes)
1E2E4-1E323 ($40 bytes)
1E331-1E332 ($2 bytes)
1E33C-1E33D ($2 bytes)
And there you have it.
Just FYI - my intention in making this patch was that the strength of the Salved item would be 4x normal strength, then divided by the number of party members. it seems like, in practice, it actually ends up being slightly less than that. I tried it with a four-member party, and a character using Item seemed to get better results on a single target than the Salve-er gets on each individual target. Not significantly, mind you (~10 HP difference for cure1, <100 HP difference for cure2 and 100-200 HP difference for cure3), but I just thought it was worth mentioning. Of course, it might be that I just kept getting really unlucky in my tests.

So, here's the patch.
Sweet - I'm Golbez now
Hehe, I forgot all about that, how time flies... I should have been more exact Chillyfeez, since I'm a bit out of practice, what LoRom Banks are those occupying? That's what I probably should have asked in the first place.