Note: This answer doesn't cover the solutions exploiting glitches (screen wrapping and such) and alternative ways (such as stealing the shovel). There might be a way to get the Level 2 sword much earlier (so far I think I can get 15 - got 12 - seashells with only the sword and the stolen shovel if I use the screen wrapping). I might try to document this later, but feel free to comment/post your own answer if you know a way.
According to this page (which lists only the requirements to get the seashells, not to get where they are located), one could get 13 seashells only having the Sword, the Roc's Feather, the Power Bracelet, the Deluxe Shovel and some Bombs (in the order you should get them (from the numbers they have on the link above), specifically for #6 and #11). Please note that unless otherwise mentioned, they all require the Power Bracelet1 to be reached:
- #1 (Sword only)
- #3 (Deluxe Shovel2 only)
- #4 (Magic Powder3 to reach the key to the Dungeon; then Bombs4)
- #14 (Power Bracelet1, with bombs and Roc's Feather to reach the emplacement, then Deluxe Shovel 2 to get the seashell)
Once you have obtained the Pegasus Boots, you can get four more seashells (which brings the total to 17): #10, #12, and also (after accessing the animal village area) #20 and #21.
In addition, after completion of the third dungeon, Marin will help moving the Walrus away, and therefore the player can access the seashell #16.
As soon as you get the flippers, you can reach the two missing seashells to obtain the Level two sword: #18 and #19.
That means that the earliest moment you can have the level two sword is after getting the flippers from the fourth dungeon (it is not required to beat the boss - you need, however, to kill the bosses of the first three dungeons, since Bowwow is required to access the second dungeon, Richard is needed to access the third one; and Marin has to sing for the Walrus for you to both access to the flippers in the fourth dungeon and to the seashell #16).
Also, from all the information I could find, the DX version does not differ from the original one on that point.
1 Needs the Sword, the Roc's Feather and some Magic Powder to be accessed.
2 Costs 200 Rupees. Usually affordable after the second Dungeon.
3 Needs the Sword to access, part of the main plot.
4 Costs 10 Rupees.
Post Scriptum: Should you need to orient yourself, I found a very handy complete map (spoilers ahead!):