As an example, is "With grace, she danced." instead of "She danced with grace" proper? It seems to me that "with grace" is an adverb phrase, similar to "gracefully", so it should be able to be used in the same way. ("Gracefully, she danced.") Somehow, it doesn't seem right to me though.
Is "With [noun], [subject] [verb]" acceptable instead of "[subject] [verb] with [noun]"?
Whether you use "with grace" or "gracefully", the most common word order would be "She danced gracefully/with grace".
Since English has lost its noun inflections, word order is very important to convey meaning. Deviation from that standard runs the risk of confusing the listener or reader, but that doesn't mean you shouldn't do it as long as the meaning remains clear (unless you intended to give your sentence ambiguity).
Rearranging the normal word order draws attention to what you're saying and can give your sentence poetic/stylistic effect. As such, the examples you've given would be a little unusual in spoken English, but pleasant to the eye in prose. NB, it's not really appropriate in a formal business setting.
Article on word order: http://en.wikipedia.org/wiki/Word_order#Functions_of_sentence_word_order and another article about anastrophe (reversal or normal word order as a rhetorical device): http://en.wikipedia.org/wiki/Anastrophe