i would encourage you to consider a few things before you let anyone pierce your child's ears.
there are a lot of good reasons why it is hard to find someone reputable that will do this on a 4 year old.
i was a piercer for over a decade and worked to write some of the laws that helped to clean up this still under regulated art.
her size and age will make it very hard for anyone to pierce her in a way that assures the holes will be equal or in the right place once she grows up.
most good professional places that use the proper tools will not work on folks this young for many reasons including what i just stated.
the cheep mall stores are more disgusting and damaging to the ear than you can possibly imagine.
the multi billion dollar companies that make those guns the mall stores use have lobbied very hard to make sure that those folks do not have to be as clean as the professional piercers do in most states. in one state even going as far as to get the ear declared not a "part of the body" to make it ok to treat it different. really just think why is it ok to use it on a ear if it is against the law to use it anywhere else on a body, even on the upper in in most states?
piercing guns are violent and aggressive in ripping a hole in tissue by shoving a only semi pointy object thru it and then that is not the right shape or size to allow for good cleaning or healing.
is she really ready? can she understand and have the self control to keep her hands off of them as the heal and itch and sit still and participate in the aftercare that will take a few months?
in my shop the youngest i ever did way a very together 7 year old, she was really ready and understood what i was going to do and held still and basically had a great time of things. at that age they deal with the pain very good actually.
she needs to be old enough to understand that she can't change the earrings for about 4 months in ear lobes and even then needs to have them changed very carefully and might have to do aftercare over again from time to time if she catches her eating on her hair or playing with a friend.
i am extremely against infant ear piercing, to me it is altering someone else's body without their consent, i huge no no. When it comes to young children i think it is just important for us to give it the weight of understanding that it is not harmless, and comes with risks and downsides. Then we can make a good choice with our children as to if they are really ready.
for my own kids, i am going to prefer to aim for about 8 or 9 and make it a wonderful thing they get to look forward to as a small but important right of passage.
here is some good reading for you:
http://www.safepiercing.org/piercing/faq/#guns
and as for the general question about finding a piercer, once you decide that you are ready for that:
http://www.safepiercing.org/piercing/choosing-a-piercer/
one final note, I'm glad your pediatrician turns folks down, frankly they may be trained in tons of things, but piercing is rarely one of them, they really should not be doing it on anyone. i get that this is at least for cleanliness, i big step up from the mall, but i think those folks should be outlawed too.
good luck with your choices, sorry is i sound a bit intense about this, it is something a care deeply about
Follow Mothering