string replacement with random element in Python

I am trying to make a fun, randomized madlibs story for my colleagues. The idea is to have them submit adjectives, nouns, and verbs, which I will add to a separate lists. I have also added markers (e.g. "(noun)") to the story as replaceables. I am trying to figure out how to replace each marker in the string with a random, UNIQUE choice from the appropriate list of nouns, adjectives, or verbs.

My first idea has a couple of bugs:

import random

nouns = ["bee","hammer","person"]
adj = ["dazzling","punctual","dizzy","petite"]
verbs = ["sprint","blab","sniff","die"]

story = "blah blah blah (noun). Blah blah blah (adj), blah blah (verb) blah blah. Blah blah blah (noun) blah blah (noun)s blah blah (verb)."

spl_story = story.split()

for i in spl_story:
    if i == "(noun)":
        i = random.choice(nouns)
#same if statement for adjectives and verbs

new_story = " ".join(spl_story)

There are 2 main issues with this:

1. if there is a "s" for a plural value (e.g. "(noun)s") or a special character after the marker, it doesn't split properly. I want to find a way to keep my punctuation and the s character, but make sure that the markers split properly.

I could do a long string of conditionals, such as:

    if i == "(noun)"
        i = random.choice(nouns)
    elif i == "(noun)s"
        i = random.choice(nouns) + "s"
    elif i == "(noun).":
        i = random.choice(nouns) + "."

but that's inefficient and I'd like to find a smoother solution.

Secondly: I need a UNIQUE choice from the list without replacing repetative nouns, verbs, etc.

My solution might suck from the get-go and if anyone thinks it would be good to throw it away and go a different path, I'm all ears. Thanks for any advice!